解题过程
中午吃饭比较晚，到机房lfw开始发各队的账号密码，byf开始读D题,shl电脑卡的要死,启动中...然后听到谁说A题过了好多，然后shl让blf读A题，A题blf一下就A了。然后lfw读完M题（shl的电脑终于打开了，然后输入密码，密码错误。。。自闭），说AC 自动机板题，然后找板子，，，突然发现自己读错题目。后来不知道怎么A的。shl copy了一遍密码终于登上账号。然后lfw一个人用单调栈和前缀和st表A掉了I题；byf 秒了H题；
shl和byf读j题，读完吧题意告诉lfw,lfw说水题，然后树链剖分加线段树离线就过了。同时byf在想K题，然后推出式子，利用前缀和就过了(听说好多对TLE了，应该没用前缀和维护)；然后还有一个多小时，，，shl和byf看D题,lfw看C题，然后shl和byf没啥想法，lfw调C调了一万年，最后也没过。。。这场每一题都是一下就过了，罚时较少。(这场shl全场OB,没碰键盘，状态极差...)
C题要注意一下，java 的BigInteger运算比c++用数组模拟高精度快，lfw被卡住了，c++要几分钟预处理，java几乎1s出来,所以最后用java，但是看错题没看到要字典序最小，没时间改
第二天改好了，最后java也超时。。。要矩阵乘法预处理出28个数。。。
题解
先放代码，题解后面更新。
A. PERFECT NUMBER PROBLEM
#include<bits/stdc++.h>
using namespace std;
int main()
{
printf("6\n");
printf("28\n");
printf("496\n");
printf("8128\n");
printf("33550336\n");
return ;
}
B. Greedy HOUHO
Unsolved.
C. Angry FFF Party
Unsolved.
lfw的题解链接 https://blog.csdn.net/liufengwei1/article/details/89522815
import java.lang.reflect.Array;
import java.util.*;
import java.math.*;
import java.io.FileOutputStream;
import java.io.PrintStream;
public class Main
{
public static BigInteger[][] multi(BigInteger [][]a,BigInteger [][]b)
{
BigInteger [][]c= new BigInteger[3][3];
for(int i=1;i<=2;i++)
for(int j=1;j<=2;j++)
c[i][j]=BigInteger.ZERO;
for(int i=1;i<=2;i++)
for(int j=1;j<=2;j++)
for(int k=1;k<=2;k++) {
c[i][k] = c[i][k].add(a[i][j].multiply(b[j][k]));
}
return c;
}
public static BigInteger qp(int b)
{
BigInteger ans[][]=new BigInteger[3][3];
BigInteger cnt[][]=new BigInteger[3][3];
ans[1][1]=BigInteger.ONE;ans[1][2]=BigInteger.ZERO;
ans[2][1]=BigInteger.ZERO;ans[2][2]=BigInteger.ONE;
cnt[1][1]=BigInteger.ZERO;cnt[1][2]=BigInteger.ONE;
cnt[2][1]=BigInteger.ONE;cnt[2][2]=BigInteger.ONE;
while(b>0)
{
if(b%2==1)
ans=multi(ans,cnt);
cnt=multi(cnt,cnt);
b>>=1;
}
return ans[2][2];
}
public static void main(String args[])
{
int []f=new int [100];
int []ans=new int[100];
int up=0,cnt=3;
f[1]=1;f[2]=1;
for(int i=3;i<=28;i++)
f[i] = f[i - 2] + f[i - 1];
//PrintStream ps=new PrintStream("B.");
BigInteger []num=new BigInteger[30];
BigInteger a,b,w,sum=BigInteger.ZERO,tmp=BigInteger.ZERO;
a=BigInteger.ONE;
b=BigInteger.ONE;
num[1]=BigInteger.ONE;
num[2]=BigInteger.ONE;
num[3]=BigInteger.ONE;
Scanner input=new Scanner(System.in);
int id=0;
//System.out.println("a[1]=1;");
//System.out.println("a[2]=1;");
//System.out.println("a[3]=1;");
id=4;
for(int i=4;i<=28;i++)
num[i]=qp(f[i]-1);
int t,anscnt;
t=input.nextInt();
while(t>0)
{
t--;sum=BigInteger.ZERO;
w=input.nextBigInteger();
anscnt=0;
for(int i=28;i>=1;i--)
{
tmp=sum.add(num[i]);
if(tmp.compareTo(w)<=0) {
sum = tmp;
ans[++anscnt] = i;
}
}
if(sum.equals(w))
{
if(ans[anscnt]==5)
{
ans[anscnt]=1;ans[++anscnt]=2;ans[++anscnt]=3;
ans[++anscnt]=4;
}
else if(ans[anscnt]==4)
{
ans[anscnt]=1;
ans[++anscnt]=2;
}
else if(ans[anscnt]==3)
{
if(ans[anscnt-1]==4)
{
ans[anscnt-1]=3;
ans[anscnt]=1;
ans[++anscnt]=2;
}
else
ans[anscnt]=1;
}
else if(ans[anscnt]==2)
{
if(ans[anscnt-1]==3)
{
ans[anscnt - 1] = 1; ans[anscnt] = 2;
}
} Arrays.sort(ans,1,anscnt+1);
for(int j=1;j<=anscnt;j++)
{
if(j>1)
System.out.print(" ");
System.out.print(ans[j]);
}
System.out.println("");
}
else
System.out.println("-1");
}
}
}
D. Match Stick Game
Unsolved.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int num[]={,,,,,,,,,};
ll f[][][];
inline void init()
{
for (int i=;i<;i++)
for (int j=;j<;j++)
f[][i][j]=-1e10;//max
memset(f[],INF,sizeof(f[]));//min
f[][][]=;
f[][][]=;
for (int i=;i<=;i++)
for (int j=;j<=i*;j++)
for (int k=;k<=;k++)
{
if(j<num[k]) continue;
f[][i][j]=min(f[][i][j],f[][i-][j-num[k]]*+k);
f[][i][j]=max(f[][i][j],f[][i-][j-num[k]]*+k);
}
}
ll dp[][];
char s[];
int nums[];
int main()
{
init();
int T,n;
scanf("%d",&T);
while(T--)
{
int tot=;
scanf("%d%s",&n,s);
for(int i=;i<=n;i++)
for(int j=;j<=n*;j++)
dp[i][j]=-1e12;//dao di i kuai haisheng j gen de max
int last=-,cnt=;
for(int i=;s[i];++i)//tongji mubang de numbers
{
if(s[i]=='+'||s[i]=='-')
{
nums[cnt++]=i-last-;
last=i;
}
if(s[i]=='+') tot+=;
else if(s[i]=='-') tot+=;
else tot+=num[s[i]-''];
}
nums[cnt++]=strlen(s)--last;
for(int i=;i<=min(nums[]*,tot);++i)
dp[][tot-i]=max(dp[][tot-i],f[][nums[]][i]);
for(int i=;i<cnt;++i)
for(int j=;j<=tot;++j)
for(int k=;k<=min(nums[i]*+,j);++k)
{
dp[i][j-k]=max(dp[i][j-k],dp[i-][j]-f[][nums[i]][k-]);//-
dp[i][j-k]=max(dp[i][j-k],dp[i-][j]+f[][nums[i]][k-]);//+
}
printf("%lld\n",dp[cnt-][]);
}
return ;
}
E. Card Game
Unsolve.
F. Information Transmitting
Unsolved.
G. tsy's number
byf题解南昌网络赛tsy's number(莫比乌斯反演&线性递推)
H. Coloring Game
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+;
int quick_pow(int a,int b)
{
int ans=;
while(b)
{
if(b&) ans=ans*a%mod;
a=a*a%mod;
b>>=;
}
return ans;
}
int32_t main()
{
int n;
scanf("%lld",&n);
if(n==) {printf("1\n");return ;}
printf("%lld\n",**quick_pow(,n-)%mod);
return ;
}
I. Max answer
#include<bits/stdc++.h>
#define maxl 500010
using namespace std; int n,top,lg;
long long ans=;
long long s[maxl];
long long a[maxl],sum[maxl],dol[maxl],dor[maxl];
long long mini[][maxl],mx[][maxl];
map <long long,int> mp;
map <long long,int> :: iterator it; inline void prework()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%lld",&a[i]),sum[i]=sum[i-]+a[i];
top=;int l=,r=;
while(l<=n && r<=n)
{
while(a[l]<= && l<=n)
l++;
if(a[l]>)
{
r=l;
while(a[r+]>)
r++;
top=;s[]=l-;
for(int i=l;i<=r;i++)
{
while(top> && a[i]<a[s[top]])
{
dor[s[top]]=i;
top--;
}
s[++top]=i;dol[i]=s[top-];
}
while(top>)
dor[s[top]]=r+,top--;
for(int i=l;i<=r;i++)
ans=max(ans,(sum[dor[i]-]-sum[dol[i]])*a[i]);
}
else r=l;
l=r+;
}
} inline void mainwork()
{
int lg=log2(n),t;
for(int i=;i<=n;i++)
mx[][i]=mini[][i]=sum[i];
for(int i=;i<=lg;i++)
for(int j=;j<=n;j++)
{
mx[i][j]=max(mx[i-][j],mx[i-][j+(<<(i-))]);
mini[i][j]=min(mini[i-][j],mini[i-][j+(<<(i-))]);
}
long long mxx,mii;
for(int i=;i<=n;i++)
if(a[i]<)
{
t=log2(i-+);
mxx=max(mx[t][],mx[t][i-(<<t)+]);
t=log2(n-i+);
mii=min(mini[t][i],mini[t][n-(<<t)+]);
ans=max((mii-mxx)*a[i],ans);
}
} inline void print()
{
printf("%lld",ans);
} int main()
{
prework();
mainwork();
print();
return ;
}
J. Distance on the tree
#include<bits/stdc++.h>
#define maxl 200010
#define inf 2000000001
using namespace std; int n,nn,q,cnt=,nodecnt=,num=;
int a[maxl],dep[maxl],tot[maxl],son[maxl],top[maxl],fa[maxl],ehead[maxl];
int idx[maxl],dy[maxl],ans[maxl];
struct ed
{
int to,nxt;
}e[maxl<<];
struct node
{
int l,r,sum;
}tree[maxl<<];
struct qu
{
int u,v,w,id;
}que[maxl],edg[maxl<<];
char ch[maxl]; inline void adde(int u,int v)
{
e[++cnt].to=v;e[cnt].nxt=ehead[u];ehead[u]=cnt;
} void dfs1(int u,int f)
{
int v;
dep[u]=dep[f]+;fa[u]=f;tot[u]=;
for(int i=ehead[u];i;i=e[i].nxt)
{
v=e[i].to;
if(v==f) continue;
dfs1(v,u);
tot[u]+=tot[v];
if(tot[v]>tot[son[u]])
son[u]=v;
}
} void dfs2(int u,int topf)
{
int v;
idx[u]=++nodecnt;dy[nodecnt]=u;
top[u]=topf;
if(!son[u]) return;
dfs2(son[u],topf);
for(int i=ehead[u];i;i=e[i].nxt)
{
v=e[i].to;
if(idx[v]) continue;
dfs2(v,v);
}
} void build(int k,int l,int r)
{
tree[k].l=l;tree[k].r=r;
if(l==r)
{
tree[k].sum=;
return;
}
int mid=(l+r)>>;
build(k<<,l,mid);
build(k<<|,mid+,r);
tree[k].sum=tree[k<<].sum+tree[k<<|].sum;
} inline bool cmp(const qu &x,const qu &y)
{
return x.w<y.w;
} inline void prework()
{
scanf("%d%d",&n,&q);
int u,v,w;num=n;
nn=n;
for(int i=;i<=n-;i++)
{
scanf("%d%d%d",&u,&v,&w);
num++;edg[i]=qu{u,v,w,num};
adde(u,num);adde(num,v);
adde(v,num);adde(num,u);
}
for(int i=;i<=q;i++)
{
scanf("%d%d%d",&que[i].u,&que[i].v,&que[i].w);
que[i].id=i;;
}
sort(edg+,edg++n-,cmp);
sort(que+,que++q,cmp);
n=num;
dfs1(,);
dfs2(,);
build(,,n);
} void add(int k,int l)
{
if(tree[k].l==tree[k].r)
{
tree[k].sum++;
return;
}
int mid=(tree[k].l+tree[k].r)>>;
if(l<=mid)
add(k<<,l);
else
add(k<<|,l);
tree[k].sum=tree[k<<].sum+tree[k<<|].sum;
} int getsum(int k,int l,int r)
{
if(tree[k].l==l && tree[k].r==r)
return tree[k].sum;
int mid=(tree[k].l+tree[k].r)>>;
if(l>mid)
return getsum(k<<|,l,r);
else
if(r<=mid)
return getsum(k<<,l,r);
else
return getsum(k<<,l,mid)+getsum(k<<|,mid+,r);
} inline int gettreesum(int x,int y)
{
int ans=;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
ans+=getsum(,idx[top[x]],idx[x]);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
ans+=getsum(,idx[x],idx[y]);
return ans;
//printf("%d\n",ans);
} inline void mainwork()
{
//int x,y;
/*scanf("%d",&q);
for(int i=1;i<=q;i++)
{
scanf("%s",ch);
scanf("%d%d",&x,&y);
if(ch[0]=='C')
{
a[x]=y;
add(1,idx[x]);
}
else if(ch[1]=='S')
gettreesum(x,y);
else
gettreemax(x,y);
}*/
int edind=;
for(int i=;i<=q;i++)
{
while(edind<nn- && edg[edind+].w<=que[i].w)
++edind,add(,idx[edg[edind].id]);
ans[que[i].id]=gettreesum(que[i].u,que[i].v);
}
} inline void print()
{
for(int i=;i<=q;i++)
printf("%d\n",ans[i]);
} int main()
{
prework();
mainwork();
print();
return ;
}
K. MORE XOR
#include<bits/stdc++.h>
using namespace std;
const int size=1e5+;
#define int long long
int sum[][size];
int arr[size];
int32_t main()
{
int t;
scanf("%lld",&t);
int n;
while(t--)
{
scanf("%lld",&n);
memset(sum,,sizeof(sum));
for(int i=;i<=n;i++)
{
scanf("%lld",&arr[i]);
}
for(int i=;i<=n;i++)
{
for(int j=;j<=;j++)
{
sum[j][i]=sum[j][i-];
}
sum[i%][i]=sum[i%][i]^arr[i];
}
int q;
scanf("%lld",&q);
int l,r;
while(q--)
{
scanf("%lld%lld",&l,&r);
int len=r-l+;
if(len%==) printf("0\n");
else if(len%==)
{
int b=l%;
printf("%lld\n",sum[b][l-]^sum[b][r]);
}
else if(len%==)
{
int b=l%,c=(l+)%;
printf("%lld\n",sum[b][l-]^sum[b][r]^sum[c][l-]^sum[c][r]);
}
else if(len%==)
{
int c=(l+)%;
printf("%lld\n",sum[c][l-]^sum[c][r]);
}
}
}
return ;
}
L. qiqi'tree
Unsolved.
M. Subsequence
#include<bits/stdc++.h>
#define maxl 100010 int slen,tlen,n;
int nxt[maxl][];
int nxtind[];
char s[maxl],t[maxl]; inline void prework()
{
scanf("%s",s+);
slen=strlen(s+);
for(int i=;i<;i++)
nxtind[i]=maxl-;
for(int i=slen;i>=;i--)
{
for(int j=;j<;j++)
nxt[i][j]=nxtind[j];
nxtind[s[i]-'a']=i;
}
for(int j=;j<;j++)
nxt[][j]=nxtind[j];
} inline bool check()
{
tlen=strlen(t+);
int u=;
for(int i=;i<=tlen;i++)
{
u=nxt[u][t[i]-'a'];
if(u== || u>slen)
return false;
}
return true;
} inline void mainwork()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%s",t+);
if(check())
puts("YES");
else
puts("NO");
}
} int main()
{
prework();
mainwork();
return ;
}
shl聚菜。%lfw.%byf.