解题过程
开场开A，A题shl看错题意，被制止。然后开始手推A，此时byf看错E题题意，开始上机。推出A的规律后，shl看了E题，发现题意读错。写完A题，忘记判断N=0的情况，WA+1。过了A后，shl重新写E，lfw开始开J题，E题过不了样例，lfw多次起立让shl调试，然后shl拿到E的一血，lfw之后过了J。byf开始开I题，shl口胡出M做法，然后lfw和shl一起推G题。byf过了I题后，shl推出G题，byf去写。然后lfw开始计算几何，经过查错后过掉，然后shl开始开M题，过掉后还剩最后半小时，无题可做。
最后罚时很多，因为前期签到题过得太慢，A题40+分钟才过,J题1小时40分钟才过。
题解
A - Adrien and Austin
题解：给你n给石头，下标依次为1~n,然后两个人轮流取石头，每次取1~k个连续下标的石头，最后不能取得输掉比赛。问你谁会获胜。
找规律，首先,n==0时，第一个人必败。k==1时,n为奇数时先手必胜。k>1时,先手必胜.
参考代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod=1e9+;
LL quick_pow(LL a,LL b)
{
LL ans=;
while(b)
{
if(b&) ans=ans*a%mod;
a=a*a%mod;
b>>=;
}
return ans;
}
int main()
{
int t;
scanf("%d",&t);
int l24=quick_pow(,mod-);
while(t--)
{
int n;
scanf("%d",&n);
LL ans=;
ans=ans*n%mod;
ans=ans*(n+)%mod;
ans=ans*(n+)%mod;
ans=ans*(n+)%mod;
ans=ans*l24%mod;
printf("%lld\n",ans);
}
}
B - Tournament
Unsolved.
C - Cherry and Chocolate
Unsolved.
D - Country Meow
队友写的.题解：https://blog.csdn.net/liufengwei1/article/details/89303612
参考代码：
#include<bits/stdc++.h>
#define maxl 110
#define eps 1e-8
struct point
{
double x,y,z;
point(double a=,double b=,double c=)
{
x=a;y=b;z=c;
}
}; int npoint,nouter;
point pt[maxl],outer[],res;
double radius,tmp,ans; inline double dist(point p1,point p2)
{
double dx=p1.x-p2.x,dy=p1.y-p2.y,dz=p1.z-p2.z;
return (dx*dx+dy*dy+dz*dz);
} inline double dot(point p1,point p2)
{
return p1.x*p2.x+p1.y*p2.y+p1.z*p2.z;
} inline void ball()
{
point q[];double m[][],sol[],L[],det;
int i,j;
res.x=res.y=res.z=radius=;
switch(nouter)
{
case : res=outer[];break;
case :
res.x=(outer[].x+outer[].x)/;
res.y=(outer[].y+outer[].y)/;
res.z=(outer[].z+outer[].z)/;
radius=dist(res,outer[]);
break;
case :
for(int i=;i<;i++)
{
q[i].x=outer[i+].x-outer[].x;
q[i].y=outer[i+].y-outer[].y;
q[i].z=outer[i+].z-outer[].z;
}
for(int i=;i<;i++)
for(int j=;j<;j++)
m[i][j]=dot(q[i],q[j])*;
for(int i=;i<;i++)
sol[i]=dot(q[i],q[i]);
if(fabs(det=m[][]*m[][]-m[][]*m[][])<eps)
return;
L[]=(sol[]*m[][]-sol[]*m[][])/det;
L[]=(sol[]*m[][]-sol[]*m[][])/det;
res.x=outer[].x+q[].x*L[]+q[].x*L[];
res.y=outer[].y+q[].y*L[]+q[].y*L[];
res.z=outer[].z+q[].z*L[]+q[].z*L[];
radius=dist(res,outer[]);
break;
case :
for(int i=;i<;i++)
{
q[i].x=outer[i+].x-outer[].x;
q[i].y=outer[i+].y-outer[].y;
q[i].z=outer[i+].z-outer[].z;
sol[i]=dot(q[i],q[i]);
}
for(int i=;i<;i++)
for(int j=;j<;j++)
m[i][j]=dot(q[i],q[j])*;
det=m[][]*m[][]*m[][]
+ m[][]*m[][]*m[][]
+ m[][]*m[][]*m[][]
- m[][]*m[][]*m[][]
- m[][]*m[][]*m[][]
- m[][]*m[][]*m[][];
if(fabs(det)<eps) return;
for(int j=;j<;j++)
{
for(int i=;i<;i++)
m[i][j]=sol[i];
L[j]=(m[][]*m[][]*m[][]
+m[][]*m[][]*m[][]
+m[][]*m[][]*m[][]
-m[][]*m[][]*m[][]
-m[][]*m[][]*m[][]
-m[][]*m[][]*m[][])/det;
for(int i=;i<;i++)
m[i][j]=dot(q[i],q[j])*;
}
res=outer[];
for(int i=;i<;i++)
{
res.x+=q[i].x*L[i];
res.y+=q[i].y*L[i];
res.z+=q[i].z*L[i];
}
radius=dist(res,outer[]);
}
} inline void minball(int n)
{
ball();
if(nouter<)
for(int i=;i<n;i++)
if(dist(res,pt[i])-radius>eps)
{
outer[nouter]=pt[i];
++nouter;
minball(i);
--nouter;
if(i>)
{
point Tt=pt[i];
memmove(&pt[],&pt[],sizeof(point)*i);
pt[]=Tt;
}
}
} inline double smallest_ball()
{
radius=-;
for(int i=;i<npoint;i++)
if(dist(res,pt[i])-radius>eps)
{
nouter=;
outer[]=pt[i];
minball(i);
}
return sqrt(radius);
} inline void prework()
{
for(int i=;i<npoint;i++)
scanf("%lf%lf%lf",&pt[i].x,&pt[i].y,&pt[i].z);
} inline void mainwork()
{
ans=smallest_ball();
} inline void print()
{
printf("%.5f\n",ans);
} int main()
{
while(~scanf("%d",&npoint))
{
prework();
mainwork();
print();
}
return ;
}
E - Eva and Euro coins
题解：给你两个01串，然后连续k个0可以翻转为1，连续k个1可以翻转为0.问你这两个01串是否可以变成相同的串。
可以利用归约。连续k个0或1可以归约掉。最后判断是否相同即可。
参考代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+;
char s[maxn],t[maxn];
int cnt[maxn][];
int n,k,tmp;
void work(char st[])
{
memset(cnt,,sizeof(cnt));
cnt[][]=-;tmp=;
for(int i=;i<=n;++i)
{
cnt[++tmp][]=st[i]-'';
cnt[tmp][] = cnt[tmp-][]==st[i]-''?cnt[tmp-][]+:;
if(cnt[tmp][]==k) tmp-=k;
}
for(int i=;i<=n;++i) {if(i<=tmp) st[i]=cnt[i][]+'';else st[i]='';}
}
int main()
{
scanf("%d%d",&n,&k);
scanf("%s",s+);
scanf("%s",t+);
work(s);work(t);
for(int i=;i<=n;++i) {if(s[i]!=t[i]) {puts("No");return ;}}
puts("Yes");
return ;
}
F - Frank
Unsolved.
G - Pyramid
题解：打表找规律，ans=n(n+1)(n+2)(n+3).
参考代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod=1e9+;
LL quick_pow(LL a,LL b)
{
LL ans=;
while(b)
{
if(b&) ans=ans*a%mod;
a=a*a%mod;
b>>=;
}
return ans;
}
int main()
{
int t;
scanf("%d",&t);
int l24=quick_pow(,mod-);
while(t--)
{
int n;
scanf("%d",&n);
LL ans=;
ans=ans*n%mod;
ans=ans*(n+)%mod;
ans=ans*(n+)%mod;
ans=ans*(n+)%mod;
ans=ans*l24%mod;
printf("%lld\n",ans);
}
}
H - Huge Discount
Unsolved.
I - Magic Potion
队友写的，好像是最大流，题解待更。
参考代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=;
const int maxm=1e5+;
const int inf=0x3f3f3f3f;
struct Edge{
int to,nxt,cap,flow;
}edge[maxm];
int tol;
int head[maxn];
void init(){
tol=;
memset(head,-,sizeof(head));
}
void AddEdge(int u,int v,int w,int rw=){
edge[tol].to=v;edge[tol].cap=w;edge[tol].flow=;
edge[tol].nxt=head[u];head[u]=tol++;
edge[tol].to=u;edge[tol].cap=rw;edge[tol].flow=;
edge[tol].nxt=head[v];head[v]=tol++;
}
int Q[maxn];
int dep[maxn],cur[maxn],sta[maxn];
bool bfs(int s,int t,int n){
int front=,tail=;
memset(dep,-,sizeof(dep[])*(n+));
dep[s]=;
Q[tail++]=s;
while(front<tail){
int u=Q[front++];
for(int i=head[u];i!=-;i=edge[i].nxt){
int v=edge[i].to;
if(edge[i].cap>edge[i].flow&&dep[v]==-){
dep[v]=dep[u]+;
if(v==t) return true;
Q[tail++]=v;
}
}
}
return false;
}
int dinic(int s,int t,int n){
int maxflow=;
while(bfs(s,t,n)){
for(int i=;i<n;i++) cur[i]=head[i];
int u=s,tail=;
while(cur[s]!=-){
if(u==t){
int tp=inf;
for(int i=tail-;i>=;i--)
{
tp=min(tp,edge[sta[i]].cap-edge[sta[i]].flow);
}
maxflow+=tp;
for(int i=tail-;i>=;i--){
edge[sta[i]].flow+=tp;
edge[sta[i]^].flow-=tp;
if(edge[sta[i]].cap-edge[sta[i]].flow==) tail=i;
}
u=edge[sta[tail]^].to;
}
else if(cur[u]!=-&&edge[cur[u]].cap>edge[cur[u]].flow&&dep[u]+==dep[edge[cur[u]].to]){
sta[tail++]=cur[u];
u=edge[cur[u]].to;
}
else{
while(u!=s&&cur[u]==-) u=edge[sta[--tail]^].to;
cur[u] = edge [cur[u]].nxt;
}
}
}
return maxflow;
}
int main()
{
init();
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
int ti,mi;
int ss=,t=n+m+;
int s1=,s2=;
for(int i=;i<=n;i++) AddEdge(s1,i+,);
for(int i=;i<=n;i++) AddEdge(s2,i+,);
AddEdge(ss,s1,n);
AddEdge(ss,s2,k);
for(int i=;i<=n;i++)
{
scanf("%d",&ti);
for(int j=;j<=ti;j++)
{
scanf("%d",&mi);
AddEdge(i+,n++mi,);
}
}
for(int i=;i<=m;i++)
{
AddEdge(i+n+,t,);
}
int ans=dinic(ss,t,t+);
printf("%d\n",ans);
}
J - Prime Game
队友写的，题解：https://blog.csdn.net/liufengwei1/article/details/89303678
参考代码：
#include<bits/stdc++.h>
#define maxl 1000010
using namespace std; int n;
int a[maxl],p[maxl],dy[maxl];
long long v[maxl];
bool no[maxl];
vector <int> f[maxl];
long long ans; inline void shai()
{
no[]=true;
int t,j;
for(int i=;i<maxl;i++)
{
if(!no[i]) p[++p[]]=i,dy[i]=i;
j=,t=i*p[];
while(j<=p[] && t<maxl)
{
dy[t]=p[j];
no[t]=true;
if(i%p[j]==)
break;
t=i*p[++j];
}
}
} inline void prework()
{
for(int i=;i<=p[];i++)
f[p[i]].clear();
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
int x=a[i],last=;
while(x>)
{
if(dy[x]!=last)
f[dy[x]].push_back(i);
last=dy[x];
x/=dy[x];
}
}
} inline void mainwork()
{
ans=;int l,r,len;
long long tmp;
for(int i=;i<=p[];i++)
if(f[p[i]].size()>)
{
tmp=v[n];
l=;r=;len=f[p[i]].size();
if(f[p[i]][]>)
tmp-=v[f[p[i]][]-];
for(int j=;j<len-;j++)
if(f[p[i]][j+]>f[p[i]][j]+)
{
l=f[p[i]][j]+;r=f[p[i]][j+]-;
tmp-=v[r-l+];
}
if(f[p[i]][len-]<n)
tmp-=v[n-f[p[i]][len-]];
ans+=tmp;
}
} inline void print()
{
printf("%lld\n",ans);
} int main()
{
shai();
for(long long i=;i<maxl;i++)
v[i]=i*(i+)/;
while(~scanf("%d",&n))
{
prework();
mainwork();
print();
}
return ;
}
K - Kangaroo Puzzle
随机化。。
#include<bits/stdc++.h>
using namespace std;
char s[][];
int n,m;
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;++i) scanf("%s",s[i]);
srand(time());
char str[]={'L','R','U','D'};
for(int i=;i<=;++i)printf("U");
for(int i=;i<=;++i)printf("R");
for(int i=;i<=;++i)printf("D");///////adsfag
for(int i=;i<=;++i)printf("L");
for(int i=;i<=;++i)
{
int x=rand()%;
printf("%c",str[x]);
}
puts("");
return ;
}
L - Lagrange the Chef
Unsolved.
M - Mediocre String Problem
题解：给你两个字符串。让你从s1中取l,r一个子串，s2的前缀，把s2的前缀放到s1的后面，组成一个回文串，问你you多少种组合方式。
我们可以把它转化为选l,x,r 和f使得l~x和1~f对称,把s1翻转,用exkmp处理,x~r为回文串.然后我们可以枚举r,用Manacher处理s1,把exnext反转,然后记录前缀和.
即可。
参考代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int,int>
const int INF=0x3f3f3f3f;
const int maxn=1e6+;
char s[maxn],t[maxn];
int lens,lent;
int mynext[maxn],extend[maxn];
ll sum[maxn]; void pre_exkmp(char x[],int m,int nxt[])
{
nxt[]=m;
int j=;
while(j+<m && x[j]==x[j+]) j++;
nxt[]=j;
int k=;
for(int i=;i<m;++i)
{
int p=nxt[k]+k-;
int L=nxt[i-k];
if(i+L<p+) nxt[i]=L;
else
{
j=max(,p-i+);
while(i+j<m&&x[i+j]==x[j]) j++;
nxt[i]=j;
k=i;
}
}
}
void exkmp(char x[],int m,char y[],int n,int nxt[],int extend[])
{
pre_exkmp(x,m,nxt);
int j=;
while(j<n && j<m&& x[j]==y[j]) ++j;
extend[]=j;
int k=;
for(int i=;i<n;++i)
{
int p=extend[k]+k-;
int L=nxt[i-k];
if(i+L<p+) extend[i]=L;
else
{
j=max(,p-i+);
while(i+j<n&&j<m&&y[i+j]==x[j]) ++j;
extend[i]=j;
k=i;
}
}
}
char Ma[maxn<<];
int len[maxn<<];
void Manacher(char s[],int le)
{
int l=;
Ma[l++]='$'; Ma[l++]='#';
for(int i=;i<le;++i) Ma[l++]=s[i],Ma[l++]='#';
Ma[l]=;
int mx=,id=;
for(int i=;i<l;++i)
{
len[i]=mx>i?min(len[*id-i],mx-i):;
while(Ma[i+len[i]]==Ma[i-len[i]]) len[i]++;
if(i+len[i]>mx) mx=i+len[i],id=i;
}
}
//moban ll getsum(int l,int r)
{
if(l>r) return ;
else if(l<=) return sum[r];
else return sum[r]-sum[l-];
} int main()
{
scanf("%s%s",s,t);
lens=strlen(s);lent=strlen(t);
Manacher(s,lens);//len[]
reverse(s,s+lens);
exkmp(t,lent,s,lens,mynext,extend);
reverse(extend,extend+lens);
sum[]=extend[];
for(int i=;i<lens;++i) sum[i]=sum[i-]+extend[i];
ll ans=;
for(int i=;i<*lens+;++i)
{
int cnt=len[i]-;
if(cnt== || len[i]==) continue;
if(cnt&)
{
int w=(i-)/;
int r=w-;
int l=w-len[i]/;
ans+=getsum(l,r);
}
else
{
int w=(i--)/;
int r=w-;
int l=w-cnt/;
ans+=getsum(l,r);
}
}
printf("%lld\n",ans); return ;
}