三月第一周
或许总结是一种好的进步方式... ## cf 1268
D1
博弈论。a[i][j], 还进行i此操作，Bob选择加j次的答案(k 归一化）。
显然，a[i][i]=i, a[i][0]=0
Alice 每次的最优决策是(a[i-1][j]+a[i-1][j-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;
const int N=2000+5;
const int mod=1e9+7;
typedef long long ll;
ll qpow(ll a,ll p){
ll ret=1;
while(p){
if(p&1) ret=(ret*a)%mod;
a=(a*a)%mod;
p>>=1;
}
return ret;
}
int a[N][N];
int main(){
int inv2=qpow(2,mod-2);
for(int i=1;i<N;++i){
for(int j=1;j<i;++j){
a[i][j]=(ll)(a[i-1][j]+a[i-1][j-1])*inv2%mod;
}
a[i][i]=i;
}
int T;
scanf("%d",&T);
while(T--){
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
printf("%lld\n",(ll)a[n][m]*k%mod);
}
return 0;
}
|
D2
计数优化。
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;
const int mod=1e9+7;
typedef long long ll;
ll qpow(ll a,ll p){
ll ret=1;
while(p){
if(p&1) ret=(ret*a)%mod;
a=(a*a)%mod;
p>>=1;
}
return ret;
}
const int N=4e6+5;
int fact[N];
int C(int n,int m){
return fact[n]*qpow(fact[m],mod-2)%mod*qpow(fact[n-m],mod-2)%mod;
}
int main(){
fact[0]=1;
for(int i=1;i<N;++i){
fact[i]=((ll)fact[i-1]*i)%mod;
}
int T;
scanf("%d",&T);
while(T--){
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
if(n==m){
printf("%lld\n",(ll)n*k%mod);
continue;
}
ll ans=0;
for(int i=1;i<=m;++i){
ans=(ans+((ll)i*qpow(2,i-1)%mod)*C(n-i-1,m-i)%mod)%mod;
}
ans=ans*qpow(qpow(2,n-1),mod-2)%mod*k%mod;
printf("%lld\n",ans);
}
return 0;
}
|
Codeforces Round #773 (Div. 2) vp
A
与x轴平行的边的，且有其他顶点在这条变下方。
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
| #include<bits/stdc++.h>
using namespace std;
int main(){
int T;
scanf("%d",&T);
while(T--){
int x1,x2,x3,y1,y2,y3;
scanf("%d%d",&x1,&y1);
scanf("%d%d",&x2,&y2);
scanf("%d%d",&x3,&y3);
int ans=0;
if(y1==y2&&y3<y1){
ans+=abs(x1-x2);
}
if(y2==y3&&y1<y2){
ans+=abs(x2-x3);
}
if(y1==y3&&y2<y1){
ans+=abs(x1-x3);
}
printf("%d\n",ans);
}
return 0;
}
|
B
人数超过power-up 的种数时，每增加一人则必须增加一点总能量。
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
| #include<bits/stdc++.h>
using namespace std;
map<int,int> mp;
int main(){
int T;
scanf("%d",&T);
while(T--){
int n,t;
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&t);
++mp[t];
}
int cnt=mp.size();
for(int i=1;i<=cnt;++i){
printf("%d ",cnt);
}
for(int i=cnt+1;i<=n;++i){
printf("%d ",i);
}
puts("");
mp.clear();
}
return 0;
}
|
C
一条成倍的数字可以结成链，从首端顺序处理即可。
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
56
57
58
| #include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int a[N];
map<int,int> mp,c;
vector<int> v[N];
int cnt;
typedef long long ll;
int main(){
int T;
scanf("%d",&T);
while(T--){
int n,x;
scanf("%d%d",&n,&x);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
}
sort(a+1,a+n+1);
for(int i=1;i<=n;++i){
++c[a[i]];
if(c[a[i]]>1) continue;
if(a[i]%x!=0){
v[++cnt].push_back(a[i]);
mp[a[i]]=cnt;
}else{
int t=a[i]/x;
if(mp[t]){
int pos=mp[t];
v[pos].push_back(a[i]);
mp[a[i]]=pos;
}else{
v[++cnt].push_back(a[i]);
mp[a[i]]=cnt;
}
}
}
int ans=0;
for(int i=1;i<=cnt;++i){
for(int j=0;j+1<v[i].size();++j){
int cp=c[v[i][j]],cn=c[v[i][j+1]];
if(cp<=cn){
c[v[i][j+1]]=cn-cp;
}else{
ans+=cp-cn;
c[v[i][j+1]]=0;
}
}
ans+=c[v[i][v[i].size()-1]];
v[i].clear();
}
mp.clear();
c.clear();
cnt=0;
printf("%d\n",ans);
}
return 0;
}
|
D
构造。找到当前处理区间与首个元素\(a[st]\)相等的除了其本身的第二个\(a[pos]\)，在\(a[pos]\)后插入使得其后数字与 \(a[st..pos-1]\)相同，然后同样的方法处理去除相同区间的字符串直到结束。
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
| #include<bits/stdc++.h>
using namespace std;
const int N=500+5;
int a[N*N];
map<int,int> mp;
typedef pair<int,int> pii;
vector<pii> ans;
vector<int> ct;
int main(){
int T;
scanf("%d",&T);
while(T--){
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
++mp[a[i]];
}
bool f=0;
for(int i=1;i<=n;++i){
if(mp[a[i]]&1){
f=1;
break;
}
}
if(f){
puts("-1");
}else{
ct.push_back(1);
int len=n,st=1;
while(st<=len){
int fd=a[st],pos=-1;
for(int i=st+1;i<=len;++i){
if(a[i]==fd){
pos=i;
break;
}
}
int p=pos+1;
for(int i=st+1;i<pos;++i,++p){
if(a[i]!=a[p]){
ans.emplace_back(p-1,a[i]);
for(int j=len+2;j>=p+2;--j){
a[j]=a[j-2];
}
a[p]=a[p+1]=a[i];
len+=2;
}
}
st=p;
ct.push_back(p);
}
printf("%d\n",ans.size());
for(auto t:ans){
printf("%d %d\n",t.first,t.second);
}
printf("%d\n",ct.size()-1);
for(int i=1;i<ct.size();++i){
printf("%d ",ct[i]-ct[i-1]);
}
puts("");
for(int i=1;i<=len;++i){
a[i]=0;
}
ans.clear();
ct.clear();
}
mp.clear();
}
return 0;
}
|
3.4 Codeforces Round #774 (Div. 2)
A
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
int T;
scanf("%d",&T);
while(T--){
ll n,s;
scanf("%lld%lld",&n,&s);
printf("%lld\n",s/(n*n));
}
return 0;
}
|
B
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;
typedef long long ll;
const int N=2e5+5;
ll a[N],sum[N];
int main(){
int T;
scanf("%d",&T);
while(T--){
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%lld",&a[i]);
}
sort(a+1,a+n+1);
for(int i=1;i<=n;++i){
sum[i]=sum[i-1]+a[i];
}
bool f=0;
for(int i=1;i+i+1<=n;++i){
if(sum[n]-sum[n-i]>sum[i+1]){
f=1;
break;
}
}
puts(f?"YES":"NO");
}
return 0;
}
|
C
\(15! > 10^9\)，分解成二的幂次即有多少个二进制位为1（popcount）。枚举分解成阶乘的什么（注意1!, 2!也是二的幂次不要枚举），popcount统计分成二的幂次部分，取最小值即可。
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll fact[16];
int main(){
fact[0]=1;
for(int i=1;i<=15;++i){
fact[i]=fact[i-1]*i;
}
int T;
scanf("%d",&T);
while(T--){
ll x;
scanf("%lld",&x);
ll rg=(1<<14);
int ans=__builtin_popcountll(x);
for(int i=0;i<rg;++i){
ll t=x;
int cnt=0;
for(int j=0;j<13;++j){
if((i>>j)&1){
++cnt;
t-=fact[j+3];
if(t<0){
cnt=-1;
break;
}
}
}
if(cnt!=-1){
ans=min(ans,cnt+__builtin_popcountll(t));
}
}
printf("%d\n",ans);
}
return 0;
}
|
3.5 Atcoder Beginer
C
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
| #include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
typedef long long ll;
ll cnt[10];
int main(){
int n;
cin>>n;
for(int i=1;i<=9;++i) cnt[i]=1;
for(int i=2;i<=n;++i){
ll nc[10];
nc[1]=(cnt[1]+cnt[2])%mod;
for(int i=2;i<=8;++i){
nc[i]=(cnt[i-1]+cnt[i]+cnt[i+1])%mod;
}
nc[9]=(cnt[8]+cnt[9])%mod;
memcpy(cnt,nc,sizeof cnt);
}
ll ans=0;
for(int i=1;i<=9;++i){
ans=(ans+cnt[i])%mod;
}
cout<<ans;
return 0;
}
|
D
递归，注意规律。
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
| #include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
char s[N];
typedef long long ll;
char g(char c,ll t){
return 'A'+(c-'A'+t)%3;
}
char f(ll t,ll k){
if(k==0) return g(s[0],t);
if(t==0) return s[k];
return g(f(t-1,k/2),k%2+1);
}
int main(){
scanf("%s",s);
int T;
scanf("%d",&T);
while(T--){
ll t,k;
scanf("%lld%lld",&t,&k);
printf("%c\n",f(t,k-1));
}
return 0;
}
|
A
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
| #include<bits/stdc++.h>
using namespace std;
const int N=100+5;
int main(){
int T;
scanf("%d",&T);
while(T--){
int n;
scanf("%d",&n);
int f0=-1,l0=-1;
for(int i=1;i<=n;++i){
int t;
scanf("%d",&t);
if(t==0){
l0=i;
if(f0==-1){
f0=i;
}
}
}
if(l0==-1){
puts("0");
}else{
printf("%d\n",l0-f0+2);
}
}
return 0;
}
|
B
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
| #include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
typedef long long ll;
int a[N];
int main(){
int T;
scanf("%d",&T);
while(T--){
int n;
scanf("%d",&n);
ll sum=0,mx=0;
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
sum=sum+a[i];
mx=max(mx,1ll*a[i]);
}
if(mx==0){
puts("0");
}else{
printf("%lld\n",sum-mx+1>=mx?1:mx-(sum-mx));
}
}
return 0;
}
|
C
注意，一个数组两两之间的积的和，排序后扫一遍可以\(O(n \log n)\)。
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
vector<int> x[N],y[N];
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
int t;
scanf("%d",&t);
x[t].emplace_back(i);
y[t].emplace_back(j);
}
}
long long ans=0;
for(int i=1;i<N;++i){
sort(x[i].begin(),x[i].end());
long long sum=0,cnt=0;
for(auto p:x[i]){
ans+=p*cnt-sum;
sum+=p;
++cnt;
}
sort(y[i].begin(),y[i].end());
sum=0,cnt=0;
for(auto p:y[i]){
ans+=p*cnt-sum;
sum+=p;
++cnt;
}
}
printf("%lld\n",ans);
return 0;
}
|
D
枚举倍数。时间复杂度 \(\sum\limits^{n}_{i=1}\frac{n}{i}=O(n \log n)\)。
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;
const int N=2e6+5;
int sum[N],cnt[N];
typedef long long ll;
int main(){
int T;
scanf("%d",&T);
while(T--){
int n,c;
scanf("%d%d",&n,&c);
for(int i=1;i<=c*2;++i){
sum[i]=cnt[i]=0;
}
for(int i=1;i<=n;++i){
int t;
scanf("%d",&t);
sum[t]=cnt[t]=1;
}
for(int i=2;i<=c*2;++i){
sum[i]+=sum[i-1];
}
bool f=1;
for(int i=1;i<=c;++i){
if(cnt[i]){
for(int j=1;(ll)j*i<=c;++j){
ll l=(ll)i*j,r=(ll)i*(j+1)-1;
if(sum[r]-sum[l-1]&&!cnt[j]){
f=0;
break;
}
}
if(!f){
break;
}
}
}
puts(f?"Yes":"No");
}
return 0;
}
|
三月第四周
odeforces Round #779 (Div. 2)
A
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
| #include<bits/stdc++.h>
using namespace std;
const int N=1e4+4;
char s[N];
int main(){
int T;
scanf("%d",&T);
while(T--){
int n;
scanf("%d%s",&n,s+1);
int ans=0;
for(int i=2;i<=n;++i){
if(s[i]=='0'){
if(s[i-1]=='0'){
ans+=2;
}else if(s[i-2]=='0'){
ans+=1;
}
}
}
printf("%d\n",ans);
}
return 0;
}
|
B
\(\gcd\) 的最大值是2。
\(n\)奇数时不存在。
\(n\)偶数时，\(1\dots n\) 中的偶（奇）数与\(p\)中的奇（偶）数匹配，答案\(\left(\left(\frac{n}{2}\right)!\right)^2\)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=998244353;
int main(){
int T;
scanf("%d",&T);
while(T--){
ll n;
scanf("%lld",&n);
ll cnt=1,ans=1;
for(int i=4;i<=n;++i){
if(!(i&1)){
++cnt;
ans*=(cnt*cnt)%mod;
ans%=mod;
}
}
cout<<((n&1)?0:ans)<<"\n";
}
return 0;
}
|
C
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;
const int N=1e5+5;
int a[N];
int main(){
int T;
scanf("%d",&T);
while(T--){
int n;
scanf("%d",&n);
bool f=1;
int c1=0,p1=-1;
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
if(a[i]==1){
++c1;
p1=i;
}
}
if(c1!=1){
f=0;
}else{
for(int i=2;i<p1;++i){
if(a[i-1]+1<a[i]){
f=0;
break;
}
}
if(f){
for(int i=p1+1;i<=n;++i){
if(a[i-1]+1<a[i]){
f=0;
break;
}
}
}
if(p1!=1){
if(a[1]-a[n]>1){
f=0;
}
}
}
if(f){
puts("YES");
}else{
puts("NO");
}
}
return 0;
}
|
D1
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll cnt[65],cc[65];
int main(){
int T;
scanf("%d",&T);
while(T--){
ll l,r;
scanf("%lld%lld",&l,&r);
memset(cnt,0,sizeof cnt);
for(ll k=l;k<=r;++k){
for(int i=0;i<63;++i){
if((k>>i)&1ll){
++cnt[i];
}
}
}
ll len=r-l+1;
memset(cc,0,sizeof cc);
for(int i=0;i<=r;++i){
ll k;
scanf("%lld",&k);
for(int i=0;i<63;++i){
if((k>>i)&1ll){
++cc[i];
}
}
}
ll ans=0;
for(int i=0;i<63;++i){
if(cnt[i]!=cc[i]){
ans|=(1ll<<i);
}
}
printf("%lld\n",ans);
}
return 0;
}
|
D2
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
56
57
58
59
60
61
62
63
64
65
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5,B=62;
int t[2][N*B];
ll val[N*B];
int cnt,root;
void insert(ll x){
bool b;int u=root;
for(int i=B;~i;--i){
b=x>>i&1ll;
if(!t[b][u])
t[b][u]=++cnt;
u=t[b][u];
}
val[u]=x;
}
ll xormax(ll x){
bool b;int u=root;
for(int i=B;~i;--i){
b=x>>i&1ll;
if(t[!b][u]) u=t[!b][u];
else u=t[b][u];
}
return x^val[u];
}
ll xormin(ll x){
bool b;int u=root;
for(int i=B;~i;--i){
b=x>>i&1ll;
if(t[b][u]) u=t[b][u];
else u=t[!b][u];
}
return x^val[u];
}
ll a[N];
int main(){
int T;scanf("%d",&T);
while(T--){
root=++cnt;
ll L,R;
scanf("%lld%lld",&L,&R);
for(ll i=L;i<=R;++i){
ll t;
scanf("%lld",&t);
a[i-L+1]=t;
insert(t);
}
int len=R-L+1;
for(ll i=1;i<=len;++i){
ll x=a[i]^L;
if(xormin(x)==L&&xormax(x)==R){
printf("%lld\n",x);
break;
}
}
for(int i=1;i<=cnt;++i){
val[i]=0;
t[0][i]=t[1][i]=0;
}
cnt=0;
}
return 0;
}
|