A. Two Screens
找两串相同前缀长度，再加上各自之后的长度
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
35
36
37
38
39
40
41
42
43
44
45
|
#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=1e5+7, mod=1e9+7;
string s,t;
int ans;
void solve(){
cin>>s>>t;
ans=0;
for(int i=0;i<min(s.size(),t.size());i++){
if(s[i]==t[i]){
ans++;
if(i==min(s.size(),t.size())-1){
ans++;
ans+=(s.size()-i)+(t.size()-i)-2;
}
}
else{
if(i!=0){
ans++;
ans+=(s.size()-i)+(t.size()-i);
}
else{
ans+=(s.size()-i)+(t.size()-i);
}
break;
}
}
cout<<ans<<endl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t=1;
cin>>t;
while(t--)solve();
return 0;
}
|
B. Binomial Coefficients, Kind Of
通过打表发现目标输出其实就是 $2^{k[i]}$
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
35
36
37
38
39
40
41
42
43
|
#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
#define int long long
const int N=1e5+7, mod=1e9+7;
ll qpow(int x,int y){
ll res=1;
while(x){
if(x&1){
res=(res*y)%mod;
}
y=(y*y)%mod;
x/=2;
}
return res;
}
void solve(){
int t;
int n[N],k[N];
cin>>t;
for(int i=1;i<=t;i++)cin>>n[i];
for(int i=1;i<=t;i++)cin>>k[i];
for(int i=1;i<=t;i++){
if(n[i]>=k[i])
cout<<qpow(k[i],2)<<endl;
else cout<<"0\n";
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t=1;
// cin>>t;
while(t--)solve();
return 0;
}
|
C. New Game
可以发现取牌只能取一段连续片段内的所有牌，那我们只需要遍历所有的牌的种类即可
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=2e5+7, mod=1e9+7;
int n,k;
void solve(){
cin>>n>>k;
map<int,int>vis;
set<int>s;
for(int i=1;i<=n;i++){
int x;
cin>>x;
s.insert(x);
vis[x]++;
}
int lst=-100,len=1;
ll tmp=0,ans=0;
for(int x:s){
if(x==lst+1){
tmp+=vis[x];
len++;
lst=x;
if(len>k){
len--;
tmp-=vis[x-k];
}
}
else{
len=1;
tmp=vis[x];
lst=x;
}
ans=max(ans,tmp);
}
cout<<ans<<endl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t=1;
cin>>t;
while(t--)solve();
return 0;
}
|
D. Attribute Checks
因为 $m$ 和 $|a[i]|$ 的值很小，可以考虑 $DP$ (开始尝试用 $set$ 实现，但是插入操作的 $nlogn$ 会使复杂度过高)
记录每种任务的需求，当遇到 $r[i]==0$ 时，即可进行dp，可以遍历所有当前总能力值前方的任务数量，取得前缀和，然后用 $dp$ 记录智力取 $i$ 时的最大 $dp$ 值
然后把用过的数组还原，将 $now+1$ 继续向下进行
最后遍历所有的 $dp$ 找到最大的值
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=2e6+7, mod=1e9+7, M=5e4+10;
int n,m;
int r[N],dp[M],st[N],in[N];
void solve(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>r[i];
}
int now=0;
int ans=0;
memset(st,0,sizeof(st));
memset(in,0,sizeof(in));
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++){
if(r[i]>0)in[r[i]]++;
if(r[i]<0)st[-r[i]]++;
if(r[i]==0||i==n){
for(int j=1;j<=now;j++){
in[j]+=in[j-1];
st[j]+=st[j-1];
}
for(int j=0;j<=now;j++){
dp[j]+=in[j]+st[now-j];
}
for(int j=now+1;j>0;j--){
dp[j]=max(dp[j],dp[j-1]);
}
now++;
for(int j=1;j<=now;j++){
in[j]=0;
st[j]=0;
}
}
}
for(int i=1;i<=now;i++)ans=max(ans,dp[i]);
cout<<ans<<endl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t=1;
// cin>>t;
while(t--)solve();
return 0;
}
|