标题怎么这么长
A. Digits Sum
(ans=frac{n}{10}+[nequiv 9 pmod {10}])
B. Reverse String
暴力枚举开始左移的点，然后暴力匹配即可。复杂度 (O(n^3))。
#include<bits/stdc++.h>
const int N=1005;
char s[N],t[N];
bool equal(int ls, int rs, int lt, int rt)
{
for(int i=ls,j=lt;i<=rs;++i,++j)
if(s[i]!=t[j]) return false;
return true;
}
int main()
{
int T; scanf("%d",&T);
while(T--)
{
scanf("%s%s",s+1,t+1);
const int ls=strlen(s+1),lt=strlen(t+1);
bool flag=true;
for(int i=1;flag&&i<=lt;++i)
{
for(int j=1;flag&&j+i-1<=ls;++j)
{
if(equal(j,j+i-1,1,i))
{
bool flag2=true;
for(int kt=i+1,ks=j+i-2;flag2&&kt<=lt;++kt,--ks)
if(ks<=0||s[ks]!=t[kt]) flag2=false;
if(flag2) flag=false;
}
}
}
puts(flag?"NO":"YES");
}
}
C. Penalty
暴搜。
#include<bits/stdc++.h>
using namespace std;
const int inf=1<<30;
char s[15];
int ans;
void solve()
{
int score[2]={0,0};
for(int i=1;i<=10;++i)
{
score[i&1]+=s[i]-'0';
if((score[0]+(10-i)/2+(i&1)<score[1])||(score[1]+(10-i)/2<score[0]))
{
ans=min(ans,i);
break;
}
}
ans=min(ans,10);
}
void dfs(int u)
{
if(u>10)
{
solve();
return ;
}
if(s[u]!='?') dfs(u+1);
else
{
s[u]='0'; dfs(u+1);
s[u]='1'; dfs(u+1);
s[u]='?';
}
}
int main()
{
int T; scanf("%d",&T);
while(T--)
{
ans=inf;
scanf("%s",s+1);
dfs(1);
printf("%d
",ans);
}
}
D. Backspace
fst 了呜呜呜
题意即为可以将串 (s) 删去首字母或者中间的任意两个字母，问能否得到串 (t)。
不难发现匹配一定是跳到奇偶性不同的位置。可以用类似序列自动机保存每个点每个字母最近的奇偶位置，直接匹配即可。（貌似也可以直接跳着匹配）注意要枚举开头，奇偶分别找一个最靠前的即可。
注意：匹配完后要判断末尾剩余的字母个数，如果为奇数个则不合法！！
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
char s[N],t[N];
int pos[2][27],ch[N][27],ls,lt;
void init()
{
for(int i=1;i<=ls;++i) memset(ch[i],0,sizeof(ch[i]));
memset(pos,0,sizeof(pos));
}
bool chk(int u)
{
for(int i=2;i<=lt;++i)
{
if(!ch[u][t[i]-'a']) return false;
u=ch[u][t[i]-'a'];
}
return (ls-u)%2==0; //<-- attention!
}
int main()
{
int T; scanf("%d",&T);
while(T--)
{
init();
scanf("%s%s",s+1,t+1);
ls=strlen(s+1),lt=strlen(t+1);
for(int i=ls;i;--i)
{
for(int j=0;j<26;++j) if(pos[~i&1][j]) ch[i][j]=pos[~i&1][j];
pos[i&1][s[i]-'a']=i;
}
bool flag[2]={false,false},Flag=true;
for(int i=1;Flag&&i<=ls;++i) if(s[i]==t[1]&&!flag[i&1])
{
flag[i&1]=true;
if(chk(i)) Flag=false;
if(flag[0]&&flag[1]) break;
}
puts(Flag?"NO":"YES");
}
}
E. Permutation Shift
orz wdzh!
题目给出 (mle frac{n}{3})，可以猜测答案很小。理性分析一波：交换次数即为 (i o a_i) 连边构图后环的个数，由于 (mle frac{n}{3})，故交换后的自环至少有 (frac{n}{3}) 个（即至少 (frac{n}{3}) 个位置不变），由此可以得出答案一定不超过 (3)。
如何找到这些答案？我们可以得到当前排列每个数为自环对应的 (k)，从而得到每个 (k) 对应的自环个数，选出符合条件的 (k) 暴力check即可。（下面代码是选了自环最多的3个check）
//orz wdzh
//the number of self-circles is no less than n/3, thus the answer is no more than 3.
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int n,k,p[N],num[N],nxt[N];
bool vis[N];
vector<pair<int,int>> v;
vector<int> ans;
void init()
{
v.clear(),ans.clear();
for(int i=1;i<=n;++i) num[i]=0;
}
bool check(int d)
{
for(int i=1;i<=n;++i) vis[i]=false;
for(int i=1;i<=d;++i) nxt[n+i-d]=p[i];
for(int i=d+1;i<=n;++i) nxt[i-d]=p[i];
int cir=0;
for(int i=1;i<=n;++i)
{
if(!vis[i]) ++cir;
int u=i;
while(!vis[u]) vis[u]=true,u=nxt[u];
}
return n-cir<=k;
}
int main()
{
int T; scanf("%d",&T);
while(T--)
{
init();
scanf("%d%d",&n,&k);
for(int i=1;i<=n;++i)
{
scanf("%d",&p[i]);
int d=(p[i]>i?n-p[i]+i:i-p[i]);
++num[d];
}
for(int i=0;i<n;++i) v.push_back(make_pair(-num[i],i));
sort(v.begin(),v.end());
for(int i=0;i<v.size()&&i<3;++i) if(check(v[i].second)) ans.push_back(v[i].second);
sort(ans.begin(),ans.end());
printf("%d ",ans.size());
for(auto x:ans) printf("%d ",x); puts("");
}
}
F. Pairwise Modulo
(a_i mod a_j iff a_i-d imes a_j(a_iin [a_j imes d, a_j imes (d+1))))，注意到条件给出所有数两两不等，这意味着我们可以对于每个 (a_j) 枚举这个 (d)，复杂度是调和级数。
每次向序列中添加一个数 (a_k)，我们需要计算已有的数对该数取模的和以及该数对已有的数取模的和，主要考虑计算上式中 (-d imes a_j) 的贡献。根据上面，我们可以枚举 (d) 把所有区间搞出来计算已有的数对该数取模的贡献，并根据之前所有数的区间计算该数对已有的数取模的贡献。可以分别用两个树状数组来进行维护。复杂度 (O(nlog ^2 n))（值域与 (n) 同级）
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
typedef long long ll;
int n,m,a[N];
ll t1[N],t2[N],ans,sum;
void upd(ll* t, int i, ll w)
{
for(;i<=m;i+=(i&-i)) t[i]+=w;
}
ll qry(ll* t, int i)
{
ll r=0;
for(;i;i-=(i&-i)) r+=t[i];
return r;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]),m=max(m,a[i]);
for(int i=1;i<=n;++i)
{
ans+=sum+1ll*a[i]*(i-1);
sum+=a[i];
ans-=qry(t1,a[i]);
for(int j=1;j*a[i]<=m;++j)
{
const int l=j*a[i],r=min(m,(j+1)*a[i]-1);
ans-=(qry(t2,r)-qry(t2,l-1))*a[i]*j;
upd(t1,l,j*a[i]),upd(t1,r+1,-j*a[i]);
}
upd(t2,a[i],1);
printf("%lld ",ans);
}
}