2019 ICPC南昌邀請賽比賽過程及題解
摘要：
解題過程
中午吃飯比較晚，到機房lfw開始發各隊的賬號密碼，byf開始讀D題,shl電腦卡的要死,啟動中...然後聽到誰說A題過了好多，然後shl讓blf讀A題，A題blf一下就A了。然後lfw讀完M題（shl的電腦終於打開了，然後輸入密碼，密碼錯誤。。。自閉），說AC 自動機板題，然後找...
解題過程
中午吃飯比較晚，到機房lfw開始發各隊的賬號密碼，byf開始讀D題,shl電腦卡的要死,啟動中...然後聽到誰說A題過了好多，然後shl讓blf讀A題，A題blf一下就A了。然後lfw讀完M題（shl的電腦終於打開了，然後輸入密碼，密碼錯誤。。。自閉），說AC 自動機板題，然後找板子，，，突然發現自己讀錯題目。後來不知道怎麼A的。shl copy了一遍密碼終於登上賬號。然後lfw一個人用單調棧A掉了I題；byf 秒了H題；
shl和byf讀j題，讀完吧題意告訴lfw,lfw說水題，然後樹鏈剖分加線段樹離線就過了。同時byf在想K題，然後推出式子，利用字首和就過了(聽說好多對TLE了，應該沒用字首和維護)；然後還有一個多小時，，，shl和byf看D題,lfw看C題，然後shl和byf沒啥想法，lfw調C調了一萬年，最後也沒過。。。這場每一題都是一下就過了，罰時較少。(這場shl全場OB,沒碰鍵盤，狀態極差...)
題解
先放程式碼，題解後面更新。
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 0;
}
View Code
B. Greedy HOUHO
Unsolved.
C. Angry FFF Party
Unsolved.
D. Match Stick Game
Unsolved.
E. Card Game
Unsolved.
F. Information Transmitting
Unsolved.
G. tsy's number
Unsolved.
H. Coloring Game
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
int quick_pow(int a,int b)
{
int ans=1;
while(b)
{
if(b&1) ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
int32_t main()
{
int n;
scanf("%lld",&n);
if(n==1) {printf("1\n");return 0;}
printf("%lld\n",2*2*quick_pow(3,n-2)%mod);
return 0;
}
View Code
I. Max answer
#include<bits/stdc++.h>
#define maxl 500010
using namespace std;
int n,top,lg;
long long ans=0;
long long s[maxl];
long long a[maxl],sum[maxl],dol[maxl],dor[maxl];
long long mini[20][maxl],mx[20][maxl];
map <long long,int> mp;
map <long long,int> :: iterator it;
inline void prework()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]),sum[i]=sum[i-1]+a[i];
top=0;int l=0,r=0;
while(l<=n && r<=n)
{
while(a[l]<=0 && l<=n)
l++;
if(a[l]>0)
{
r=l;
while(a[r+1]>0)
r++;
top=0;s[0]=l-1;
for(int i=l;i<=r;i++)
{
while(top>0 && a[i]<a[s[top]])
{
dor[s[top]]=i;
top--;
}
s[++top]=i;dol[i]=s[top-1];
}
while(top>0)
dor[s[top]]=r+1,top--;
for(int i=l;i<=r;i++)
ans=max(ans,(sum[dor[i]-1]-sum[dol[i]])*a[i]);
}
else r=l;
l=r+1;
}
}
inline void mainwork()
{
int lg=log2(n),t;
for(int i=0;i<=n;i++)
mx[0][i]=mini[0][i]=sum[i];
for(int i=1;i<=lg;i++)
for(int j=0;j<=n;j++)
{
mx[i][j]=max(mx[i-1][j],mx[i-1][j+(1<<(i-1))]);
mini[i][j]=min(mini[i-1][j],mini[i-1][j+(1<<(i-1))]);
}
long long mxx,mii;
for(int i=1;i<=n;i++)
if(a[i]<0)
{
t=log2(i-0+1);
mxx=max(mx[t][0],mx[t][i-(1<<t)+1]);
t=log2(n-i+1);
mii=min(mini[t][i],mini[t][n-(1<<t)+1]);
ans=max((mii-mxx)*a[i],ans);
}
}
inline void print()
{
printf("%lld",ans);
}
int main()
{
prework();
mainwork();
print();
return 0;
}
View Code
J. Distance on the tree
#include<bits/stdc++.h>
#define maxl 200010
#define inf 2000000001
using namespace std;
int n,nn,q,cnt=0,nodecnt=0,num=0;
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<<1];
struct node
{
int l,r,sum;
}tree[maxl<<2];
struct qu
{
int u,v,w,id;
}que[maxl],edg[maxl<<1];
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]+1;fa[u]=f;tot[u]=1;
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=0;
return;
}
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
tree[k].sum=tree[k<<1].sum+tree[k<<1|1].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=1;i<=n-1;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=1;i<=q;i++)
{
scanf("%d%d%d",&que[i].u,&que[i].v,&que[i].w);
que[i].id=i;;
}
sort(edg+1,edg+1+n-1,cmp);
sort(que+1,que+1+q,cmp);
n=num;
dfs1(1,0);
dfs2(1,1);
build(1,1,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)>>1;
if(l<=mid)
add(k<<1,l);
else
add(k<<1|1,l);
tree[k].sum=tree[k<<1].sum+tree[k<<1|1].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)>>1;
if(l>mid)
return getsum(k<<1|1,l,r);
else
if(r<=mid)
return getsum(k<<1,l,r);
else
return getsum(k<<1,l,mid)+getsum(k<<1|1,mid+1,r);
}
inline int gettreesum(int x,int y)
{
int ans=0;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
ans+=getsum(1,idx[top[x]],idx[x]);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
ans+=getsum(1,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=0;
for(int i=1;i<=q;i++)
{
while(edind<nn-1 && edg[edind+1].w<=que[i].w)
++edind,add(1,idx[edg[edind].id]);
ans[que[i].id]=gettreesum(que[i].u,que[i].v);
}
}
inline void print()
{
for(int i=1;i<=q;i++)
printf("%d\n",ans[i]);
}
int main()
{
prework();
mainwork();
print();
return 0;
}
View Code
K. MORE XOR
#include<bits/stdc++.h>
using namespace std;
const int size=1e5+5;
#define int long long
int sum[4][size];
int arr[size];
int32_t main()
{
int t;
scanf("%lld",&t);
int n;
while(t--)
{
scanf("%lld",&n);
memset(sum,0,sizeof(sum));
for(int i=1;i<=n;i++)
{
scanf("%lld",&arr[i]);
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<=3;j++)
{
sum[j][i]=sum[j][i-1];
}
sum[i%4][i]=sum[i%4][i]^arr[i];
}
int q;
scanf("%lld",&q);
int l,r;
while(q--)
{
scanf("%lld%lld",&l,&r);
int len=r-l+1;
if(len%4==0) printf("0\n");
else if(len%4==1)
{
int b=l%4;
printf("%lld\n",sum[b][l-1]^sum[b][r]);
}
else if(len%4==2)
{
int b=l%4,c=(l+1)%4;
printf("%lld\n",sum[b][l-1]^sum[b][r]^sum[c][l-1]^sum[c][r]);
}
else if(len%4==3)
{
int c=(l+1)%4;
printf("%lld\n",sum[c][l-1]^sum[c][r]);
}
}
}
return 0;
}
View Code
L. qiqi'tree
Unsolved.
M. Subsequence
#include<bits/stdc++.h>
#define maxl 100010
int slen,tlen,n;
int nxt[maxl][27];
int nxtind[27];
char s[maxl],t[maxl];
inline void prework()
{
scanf("%s",s+1);
slen=strlen(s+1);
for(int i=0;i<26;i++)
nxtind[i]=maxl-1;
for(int i=slen;i>=1;i--)
{
for(int j=0;j<26;j++)
nxt[i][j]=nxtind[j];
nxtind[s[i]-'a']=i;
}
for(int j=0;j<26;j++)
nxt[0][j]=nxtind[j];
}
inline bool check()
{
tlen=strlen(t+1);
int u=0;
for(int i=1;i<=tlen;i++)
{
u=nxt[u][t[i]-'a'];
if(u==0 || u>slen)
return false;
}
return true;
}
inline void mainwork()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",t+1);
if(check())
puts("YES");
else
puts("NO");
}
}
int main()
{
prework();
mainwork();
return 0;
}
View Code
shl聚菜。%lfw.%byf.