首页 > 代码库 > NOI2014 Day1 题解。
NOI2014 Day1 题解。
自测100+100+62=262。
BUAA给出的成绩是200，T3 checker评测windows选手答案都为RE。
起床困难综合征 sleep
题意：在[0,m]中取一个整数，使得n次给定的位运算操作后（包括and&,or|,xor^），答案最大。（m<=10^9，n<=10^5）
送分题。也许是NOI2013的金牌线偏低，DZD主席希望今年分数好看些。
二进制拆分。
先计算出每一位0/1经过n次位运算的答案。
再用数位DP求出答案最大值。
时间复杂度O(nlg^m)。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<cmath> 6 #include<algorithm> 7 #define MAXN 100010 8 #define MAXD 30 9 using namespace std;10 int a[MAXN][MAXD],b[MAXD][2],d[MAXD];11 int opt[MAXN];12 int f[2][MAXD];13 int n,m;14 15 int calc(int less,int dep){16 if(dep<0) return 0;17 if(~f[less][dep]) return f[less][dep];18 int ed=less?1:d[dep],ret=0;19 for(int i=0;i<=ed;i++)20 ret=max(calc(less|(i<ed),dep-1)+b[dep][i]*(1<<dep),ret);21 f[less][dep]=ret;22 return ret;23 }24 25 int main(){26 freopen("sleep.in","r",stdin);freopen("sleep.out","w",stdout);27 scanf("%d%d",&n,&m);28 for(int j=0;j<MAXD;j++){29 d[j]=m&1;30 m>>=1;31 }32 char op[5]; int v;33 for(int i=1;i<=n;i++){34 scanf("%s%d",op,&v);35 if(op[0]==‘O‘) opt[i]=0;36 else if(op[0]==‘X‘) opt[i]=1;37 else if(op[0]==‘A‘) opt[i]=2;38 for(int j=0;j<MAXD;j++){39 a[i][j]=v&1;40 v>>=1;41 }42 }43 for(int j=0;j<MAXD;j++){44 b[j][0]=0,b[j][1]=1;45 for(int i=1;i<=n;i++)46 if(opt[i]==0) b[j][0]|=a[i][j],b[j][1]|=a[i][j];47 else if(opt[i]==1) b[j][0]^=a[i][j],b[j][1]^=a[i][j];48 else if(opt[i]==2) b[j][0]&=a[i][j],b[j][1]&=a[i][j];49 }50 memset(f,255,sizeof(f));51 printf("%d\n",calc(0,MAXD-1));52 return 0;53 }
魔法森林 forest
题意：给定一个无向图，每条边上有权值（A,B），试找出一条1->n的路径，使路径上所有边A的最大值与B的最大值之和尽量小。
令某条1->n路径上的边的集合是S，即求出min{max{Ai}+max{Bj},i∈S,j∈S}。
n<=50000,m<=100000,Ai,Bi<=50000。
LCT维护MST。（可以参考BZOJ2594，三天前刚敲过，心情大好）
按A的权值排序，逐个加入LCT。
LCT维护(u,v)路径上的边权B最大值。
若加入某条边(u,v)形成环，则删除(u,v)路径上边权B最大的边。（边可以转化为虚点，便于删除。）
加入第i条边后，用第i条边的边权A与树上B的最大值更新答案。
理论复杂度O(nlogn)。极限数据是0.5s~0.6s，时限3s有些宽了。
这题是lich出的，数据不是很理想。
没有卡掉每次松弛的SPFA，也没有卡掉（错误算法？）三分。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<cmath> 6 #include<algorithm> 7 #define MAXN 400010 8 using namespace std; 9 int n,m; 10 11 char buf[10000000],*pt = buf,*o = buf; 12 int getint(){ 13 int f = 1,x = 0; 14 while((*pt != ‘-‘) && (*pt < ‘0‘ || *pt > ‘9‘)) pt ++; 15 if(*pt == ‘-‘) f = -1,pt ++; else x = *pt++ - 48; 16 while(*pt >= ‘0‘ && *pt <= ‘9‘) x = x * 10 + *pt ++ - 48; 17 return x * f; 18 } 19 20 struct LinkCutTree{ 21 int ch[MAXN][2],key[MAXN],f[MAXN],rev[MAXN],Max[MAXN],Maxnode[MAXN]; 22 int tot; 23 int newnode(int x){ 24 int p=++tot;key[p]=Max[p]=x;Maxnode[p]=key[p]?p:0; 25 return p; 26 } 27 bool isroot(int x){ 28 return (!f[x]||ch[f[x]][0]!=x&&ch[f[x]][1]!=x); 29 } 30 void push_up(int x){ 31 if(!x) return; 32 int lc=ch[x][0],rc=ch[x][1]; 33 Max[x]=key[x];Maxnode[x]=key[x]?x:0; 34 if(lc) if(Max[lc]>Max[x]) Max[x]=Max[lc],Maxnode[x]=Maxnode[lc]; 35 if(rc) if(Max[rc]>Max[x]) Max[x]=Max[rc],Maxnode[x]=Maxnode[rc]; 36 } 37 void push_down(int x){ 38 if(!x) return; 39 int lc=ch[x][0],rc=ch[x][1]; 40 if(rev[x]){ 41 swap(ch[x][0],ch[x][1]); 42 rev[lc]^=1;rev[rc]^=1; 43 rev[x]=0; 44 } 45 } 46 void rotate(int x,int t){ 47 if(isroot(x)) return; 48 int y=f[x]; 49 ch[y][t]=ch[x][!t];if(ch[x][!t]) f[ch[x][!t]]=y; 50 f[x]=f[y];if(f[y]){ 51 if(ch[f[y]][0]==y) ch[f[y]][0]=x; 52 if(ch[f[y]][1]==y) ch[f[y]][1]=x; 53 } 54 f[ch[x][!t]=y]=x;push_up(y); 55 } 56 void splay(int x){ 57 push_down(x); 58 while(!isroot(x)){ 59 int y=f[x];push_down(y);push_down(x); 60 rotate(x,ch[y][1]==x); 61 } 62 push_up(x); 63 } 64 void init(){ 65 tot=0;for(int i=1;i<=n;i++) newnode(0); 66 } 67 void access(int v){ 68 for(int u=v,v=0;u;v=u,u=f[u]) splay(u),ch[u][1]=v; 69 } 70 void evert(int v){ 71 access(v);splay(v);rev[v]^=1; 72 } 73 int find_root(int v){ 74 access(v);splay(v);for(;ch[v][0];v=ch[v][0]);splay(v);return v; 75 } 76 void link(int u,int v){ 77 evert(u);f[u]=v; 78 } 79 void cut(int u,int v){ 80 evert(u);access(v);splay(v);f[u]=ch[v][0]=0; 81 } 82 void findmax(int u,int v,int&Mx,int&Mxnode){ 83 if(find_root(u)!=find_root(v)) return; 84 evert(u);access(v);splay(v);Mx=Max[v];Mxnode=Maxnode[v]-n; 85 } 86 int query(int u,int v){ 87 evert(u);access(v);splay(v);return Max[v]; 88 } 89 }LCT; 90 91 struct Edge{ 92 int u,v,a,b; 93 }e[410000]; 94 95 bool cmp(Edge A,Edge B){ 96 return A.a<B.a; 97 } 98 99 int solve(){100 int ret=0x7f7f7f7f;101 for(int i=1;i<=m;i++){102 if(LCT.find_root(e[i].u)!=LCT.find_root(e[i].v)){103 LCT.link(e[i].u,n+i);104 LCT.link(e[i].v,n+i);105 }106 else{107 int mx=0,id=0;LCT.findmax(e[i].u,e[i].v,mx,id);108 if(e[i].b<mx){109 LCT.cut(e[id].u,n+id);110 LCT.cut(e[id].v,n+id);111 LCT.link(e[i].u,n+i);112 LCT.link(e[i].v,n+i);113 }114 }115 if(LCT.find_root(1)==LCT.find_root(n))116 ret=min(e[i].a+LCT.query(1,n),ret);117 } 118 return (ret<0x7f7f7f7f)?ret:-1;119 }120 121 int main(){122 freopen("forest.in","r",stdin);freopen("forest.out","w",stdout);123 fread(buf,1,10000000,stdin);124 n=getint(),m=getint();125 for(int i=1;i<=m;i++) e[i].u=getint(),e[i].v=getint(),e[i].a=getint(),e[i].b=getint();126 sort(e+1,e+m+1,cmp);127 LCT.init();for(int i=1;i<=m;i++) LCT.newnode(e[i].b);128 printf("%d\n",solve());129 return 0;130 }
消除游戏 game
题意：提交答案题。N×M的方格，有K次机会，找出一条L单位长的路径，有L^C1的质数分，和L^C2的回文分。具体看题面。
game1.in
5 5 100 2 16 2 2 1
1 1 2 3 4
0 1 2 3 5
0 6 5 4 6
0 7 8 8 7
0 0 0 0 7
手玩，送分。
game2.in
10 10 100 2 8 1 1 1
7 4 1 3 5 9 8 6 1 6
8 0 9 1 1 1 1 7 1 2
9 3 6 7 5 1 5 9 6 0
8 1 8 4 9 7 7 4 3 9
0 4 0 0 9 0 1 7 8 3
8 4 8 7 3 7 8 0 7 0
7 1 6 6 1 0 5 8 9 0
5 9 9 1 1 5 1 5 1 5
8 1 2 7 6 2 3 3 3 0
0 9 1 0 9 4 0 6 1 9
注意到F=1，需要尽量消完。随机化搜索尽量取满。这个点算相对麻烦的。
game3.in game4.in C1=2,C2=0。
只有质数分。miller-Rabbin判大质数，暴搜（不用随机化）直接搜满，轻松加愉快。
game5.in
我用裸的质数暴搜取了12个8位质数。可以得到9分。
结合game2的随机化搜索可以得到满分吧。
game6-10，C1=0,C2!=0.
只有回文分。可以搜一下回文。试着找一下循环、对称，可能存在坏点。
这道提答相对容易，理清质数、回文两类，写好暴搜，可以得到50-60甚至更多的分数。（待补充随机化算法）
NOTE:提答题的数据，观察其是否随机，可以看下压缩包。压缩率达到数十倍，一般是手动构造循环。（可能含有坏点）