这次又是倒在了t5，没救了。
ABC379
A - Cyclic
难度：红
#include<bits/stdc++.h>
using namespace std;
int main(){
char a,b,c;cin>>a>>b>>c;
cout<<b<<c<<a<<' '<<c<<a<<b;
return 0;
}
B - Strawberries
难度：红
#include<bits/stdc++.h>
using namespace std;
int main(){
int k,n,cnt=0,ans=0;
cin>>n>>k;
for(int i=1;i<=n;i++){
char c;cin>>c;
if(c=='O')cnt++;
else cnt=0;
if(cnt>=k)cnt=0,ans++;
}
cout<<ans;
return 0;
}
C - Sowing Stones
难度：橙
考的时候以为要__int128，其实是不用的。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lit __int128
#define mxn 200010
#define mp make_pair
#define pll pair<ll,ll>
#define X first
#define Y second
lit sum=0;
ll now=1,n,m;
pll a[mxn];
lit ans=0;
void write(lit a){
if(a<10){
putchar('0'+a);return;
}
write(a/10);
putchar('0'+(a%10));
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++)cin>>a[i].X;
for(int i=1;i<=m;i++)cin>>a[i].Y,sum+=a[i].Y;
sort(a+1,a+m+1);
if(sum!=n||a[1].X!=1)cout<<"-1",exit(0);
a[m+1]=mp(n+1,0);
for(int i=1;i<=m;i++){
ans+=(now-a[i].X+(now+a[i].Y-a[i].X-1))*(a[i].Y)/2;
now=now+a[i].Y;
if(now<a[i+1].X||now>n+1)cout<<"-1",exit(0);
}
write(ans);
return 0;
}
D - Home Garden
难度：橙-黄
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mxn 200010
ll q,a[mxn],head=200000,tail=200000,lazy;
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>q;
while(q--){
int opt;cin>>opt;
if(opt==1)a[--head]=-lazy;//插入
else if(opt==2){//全局加
ll t;cin>>t,lazy+=t;
}
else{
ll h;cin>>h;
ll pos=lower_bound(a+head,a+tail,h-lazy)-(a+head);
cout<<tail-head-pos<<'\n',tail=head+pos;//查找并删除
}
}
return 0;
}
E - Sum of All Substrings
难度：黄
对于答案的每一位判贡献即可。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mxn 200010
ll n;char s[mxn];
ll num[mxn<<3],len,sum,ten[20];
int main(){
scanf("%lld",&n);getchar();
for(int i=1;i<=n;i++){
scanf("%c",s+i);
sum+=i*(s[i]-'0');
}
ten[0]=1;
for(ll i=1;i<=9;i++)ten[i]=ten[i-1]*10;
for(ll i=n;i;i--){
num[(n-i)/8+1]+=sum*ten[(n-i)%8];
for(ll j=(n-i)/8+1;;j++){
if(num[j]>=ten[8]){
num[j+1]+=num[j]/ten[8];
num[j]%=ten[8];
}
else{
len=max(len,j);
break;
}
}
sum-=i*(s[i]-'0');
}
for(int i=len;i;i--){
if(i==len)printf("%lld",num[i]);
else printf("%08lld",num[i]);
}
return 0;
}
F - Buildings 2
难度：黄-绿
离线处理询问。
可以用单调栈之类的东西维护最长上升子序列。
#include<bits/stdc++.h>
using namespace std;
#define mxn 200005
#define ll long long
#define pb push_back
vector<int> ask[mxn];
int n,m,a[mxn],askr[mxn],ans[mxn];
int q[mxn],tail,head;
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
tail=head=mxn-5;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=m;i++){
int l;cin>>l>>askr[i];
ask[l].pb(i);
}
for(int i=n;i;i--){
for(int id:ask[i])ans[id]=(head-tail)-(lower_bound(q+tail,q+head,askr[id]+1)-(q+tail));
while(tail<head&&a[q[tail]]<a[i])tail++;
q[--tail]=i;
}
for(int i=1;i<=m;i++)
cout<<ans[i]<<'\n';
return 0;
}
G - Count Grid 3-coloring
难度：蓝
对于每一位，我们设计 \(4\) 种状态：值为 \(1,2,3,\) 未知。对于每一位的取值至于上一行以及这一行确定的部分有关，考虑 \(\min(n,m)\leq20\)，直接暴力转移即可。时间复杂度 \(\mathcal O(2^{\min(n,m)}nm)\)。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 998244353
#define mp make_pair
#define pii pair<ll,ll>
#define mxn 210
ll n,m,l,r,k,ans;
char s[mxn][mxn];
map<ll,ll> f,g;
ll get(ll x,ll a){
return (x>>(a*2-2))&3;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>s[i][j];
if(n<m){
swap(n,m);
for(ll i=1;i<=n;i++)
for(int j=1;j<=min(i,m);j++)
swap(s[i][j],s[j][i]);
}
//对于每个点有4种情况:0,1,2,未知(3)
//所以初始为2^(m*2)位
f[(1<<m*2)-1]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
g.clear();
for(pii p:f){//上一行以及这一行确定的部分
ll X=p.first,Y=p.second;
if(s[i][j]!='?')l=r=k=s[i][j]-'0'-1;
else l=0,r=2;
for(ll k=l;k<=r;k++){
if(k==get(X,j)||(j>1&&k==get(X,j-1)))continue;
//不能与上一行以及这一行的相邻部分相同
ll num=X^((get(X,j)^k)<<(j*2-2));
//枚举可能的情况进行转移
g[num]=(g[num]+Y)%mod;
}
}
f=g;
}
}
for(pii p:f)
ans=(ans+p.second)%mod;
cout<<ans;
}