你浅浅的微笑就像~
img
牛客周赛 Round 18
A
直接输出即可
先特判前k位，ok用来特判是不是第一个0的
后面就直接正常输出即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| #include <bits/stdc++.h>
using namespace std;
int main()
{
string s;
int n,ok=0;
cin>>s>>n;
for(int i=n-1;i>=0;i--)
{
if(s[i]=='0'&&ok==0);
else cout<<s[i],ok=1;
}
for(int i=n;i<s.length();i++)
cout<<s[i];
}
|
B
数据2-10
我认为暴力都可以过（）
写一个素数
直接暴力枚举排列即可
真是一个好用的函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| #include<bits/stdc++.h>
using namespace std;
int a[100010];
int check(int n)
{
for(int i=2;i<=sqrt(n);i++){
if(n%i==0)return 0;
}
return 1;
}
int main(){
int n;
cin>>n;
int ans=0;
for(int i=0;i<n;i++)a[i]=i+1;
do{
int k=1;
for(int i=0;i<n-1;i++){
if(check(a[i]+a[i+1])){
k=0;
break;
}
}
ans+=k;
}while(next_permutation(a,a+n));
cout<<ans;
return 0;
}
|
当然本题也可以进行打表（）
1
2
3
4
5
6
7
8
9
10
11
12
13
| #include<bits/stdc++.h>
using namespace std;
int multi=false;
void solve(){
int n;cin>>n;
vector<int> res={0,0,0,0,4,24,156,1164,6312,31952};
cout<<res[n-1]<<endl;
}
signed main(){
int t=1;
if(multi)cin>>t;
while(t--)solve();
}
|
C
一天最多2套试卷，还得是K的倍数
要看最多能够刷多少天
这题介绍一下思路： 由于必须是k的倍数因此可以考虑先取模
取模后一定都是小于k的数字
这时候分情况进行讨论
：如果说取模后是0直接加上
如果说取模后是原来数字的一半，直接加上/2，向下取整
如果说是其他情况的话，那么直接加上他的m-a[i]部分的个数和他自己的个数的最小值，这一步要注意一件事情就是要把m-a[i]的个数记作0不然会wa.
实现方法自然就是STL的map
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
map<int,int>mp;
int n,k,ans=0;
cin>>n>>k;
vector<int>a(n);
for(int i=0;i<n;i++){
cin>>a[i];
a[i]%=k;
if(a[i]==0) ans++;
else mp[a[i]]++;
}
for(auto [x,y]:mp)
{
if(2*x<k&&mp[k-x]) ans+=min(y,mp[k-x]);
else if(2*x==k) ans+=y/2;
}
cout<<ans;
return 0;
}
|
D
一眼背包
至于状态，无非只是加一个上一个背包买不买罢了
只需要加一共状态就可以了
由于有3层，正序或倒序都无关紧要
前两层是正常的01背包，后一层是0表示不买，1表示买，2表示半价购买
转移很容易懂
前面买了后面可以不买，也可以买，也可以半价买
前面没买，这个可以不买，也可以买
前面半价买，这个可以买，也可以不买
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
int n, m;
vector<vector<vector<ll>>> dp;
vector<int> a, b;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> m;
dp.resize(n, vector<vector<ll>>(m + 1, vector<ll>(3, 0)));
a.resize(n), b.resize(n);
for (auto &i: a)cin >> i;
for (auto &i: b)cin >> i;
for (int i = m; i >= a[0]; --i) {
dp[0][i] = {0, b[0], 0};
}
for (int i = 1; i < n; ++i) {
for (int j = m; j >= 0; --j) {
if (j - a[i] >= 0) {
dp[i][j][1] = max(max(dp[i - 1][j - a[i]][0], dp[i - 1][j - a[i]][1]), dp[i - 1][j - a[i]][2]) + b[i];
}
dp[i][j][0] = max(max(dp[i - 1][j][0], dp[i - 1][j][1]), dp[i - 1][j][2]);
if (j - a[i] / 2 - a[i - 1] >= 0){
dp[i][j][2] = dp[i - 1][j - a[i] / 2][1] + b[i];
}
}
}
cout << max(max(dp[n - 1][m][0], dp[n - 1][m][1]), dp[n - 1][m][2]) << endl;
return 0;
}
|
