今天仍然是KCZ出题。今天才知道KCZ不仅是WZ地区史上最强选手而且还是ZJ队长？在ZJOI拿到Rank1的男人？%%%%%
今天KCZ出题的依然很强势……
T1.wzoi
期望得分20～100 实际得分100
可能KCZ也想怀念一下自己地区的OI？
这道题一开始的时候想了个贪心，暂时没发现啥反例，但是其实没什么把握，就先去把后面的题写了。
回来的时候大致想的差不多了，然后发现自己其实也不会写暴力，稳拿的只有20这个算法还能过，那就直接交吧。自己测了几组数据，也没卡掉。
后来评测发现自己A了，题解说的也是一样的。之后想懂了，一是肯定不存在不得分的做题，因为如果有的哈我们只要换一种题就能得10分。然后肯定不压题更好，所以应该有题就做。最后的想法是，是否压几道题会导致可能得分更高？不会。出现上述情况只有一种可能，就是你在压题的时候做了几道10分的题，比你不压题的时候做几道5分的题得分更多，但是这不可能，因为如果你要通过压题来获得更高的分数，你现在压的肯定不是你要做的题，否则的话你直接做就行了，然后每次你只能做最后看的题，所以这就完全没有必要了。所以这样贪心是可以的。
看一下代码。
#include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<iostream> #include<set> #include<queue> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(' ') using namespace std; typedef long long ll; const int M = 2000005; int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op; } int n,tot,stack[M],top,res,a[M]; char s[M]; int main() { freopen("wzoi.in","r",stdin); freopen("wzoi.out","w",stdout); scanf("%s",s+1); n = strlen(s+1),res = n; rep(i,1,n) a[i] = s[i] - '0'; rep(i,1,n) { if(!top) { stack[++top] = a[i],res--; continue; } if(stack[top] == a[i]) top--,tot += 10; else if(top == res) top--,tot += 5; else stack[++top] = a[i]; res--; } printf("%d ",tot); return 0; }
T2.course
期望得分10，实际得分10.
这道题当时真的不会，于是写了一发爆搜交上去，果然得了10分。（剩下全T了）当时只是注意到允许的误差范围很大（0.03），在概率题里面相当大了，不过没想到这竟然是解题的关键。
随机化！题解令人脑洞大开……题解的意思只要随机选取一些序列暴力判断，大致只要枚举10000次就可以了，误差在0.02左右……神奇。
然后自己改了大概30分钟发现相差甚远orz，概率都差了0.2了……于是看了看题解代码，过然简洁。
Ssy神犇直接用自己的随机化A了此题，可怕……
10分爆搜：
#include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<iostream> #include<set> #include<queue> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(' ') using namespace std; typedef long long ll; const int M = 100005; int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op; } struct node { int next,from,to; }e[M]; int n,pre[105],m,rdeg[105],cdeg[105],ecnt,head[205],shate,sum; char s[105],a[105],hate[6][105]; bool vis[105]; void add(int x,int y) { e[++ecnt].to = y; e[ecnt].from = x; e[ecnt].next = head[x]; head[x] = ecnt; } bool pd() { sum++; rep(i,1,m) { rep(j,1,n) { bool flag = 0; rep(k,1,hate[i][0]) { if(hate[i][k] != a[j+k-1]) { flag = 1; break; } } if(!flag) return 1; } } return 0; } void dfs(int x,int cur) { vis[x] = 1; for(int i = head[x];i;i = e[i].next) rdeg[e[i].to]--; rep(i,1,n) { if(vis[i] || rdeg[i]) continue; a[cur] = s[i]; if(cur == n) shate += pd(); else dfs(i,cur+1); a[cur] = 0; } for(int i = head[x];i;i = e[i].next) rdeg[e[i].to]++; vis[x] = 0; } int main() { freopen("course.in","r",stdin); freopen("course.out","w",stdout); n = read(); rep(i,1,n) pre[i] = read(),add(pre[i],i),rdeg[i]++; scanf("%s",s+1); m = read(); rep(i,1,m) scanf("%s",hate[i]+1),hate[i][0] = strlen(hate[i]+1); dfs(0,1); double p = double(sum - shate),q = (double)sum; printf("%.6lf ",p/q); return 0; }
std：
#include<bits/stdc++.h> using namespace std; int rand_int() { return RAND_MAX<=32768?rand():rand()*32768+rand(); } #define rep(i,l,r) for(int i=l;i<=r;++i) const int N=100+5,TOT=10000; int n; bool in[N]; int fa[N]; char s[N],q[N],t[6][25]; void rand_q() { in[0] = 1; rep(head,1,n) { int now = rand_int() % (n-head+1) + 1; int i = 1; while(now -= !in[i]) ++i; while(!in[fa[i]]) i = fa[i]; in[i] = 1,q[head] = s[i]; } } int main() { freopen("course.in","r",stdin); freopen("course.out","w",stdout); cin>>n; rep(i,1,n)scanf("%d",fa+i); scanf("%s",s+1); int m; cin>>m; rep(i,1,m)scanf("%s",t[i]+1); int ap_cnt=0; rep(tmp,1,TOT) { rand_q(); bool ap=0; rep(i,1,m) { int len_t = strlen(t[i]+1); rep(j,1,n - len_t+1) { int k=0; while(k < len_t && q[j+k] == t[i][1+k])++k; if(k == len_t) { ap = 1; break; } } if(ap)break; } ap_cnt += ap; } printf("%f ",1 - (double)ap_cnt/TOT); }
T3.painting
期望得分40，实际得分40.
这道题也是不会做orz。不过考试的时候想到，其实不合法的情况很好判断，只有初始的时候给定的k个点不合法那么才不合法，否则的话任何一种情况都是有解的。我的想法就是，使用一个multiset记录当前的最小元素，然后每次把它向四周暴力外扩，每次+d即可。这样的算法的确是正确的，然后成功骗到了40.
正解实在是没看懂……KCZ大神的T3真心看不懂……把题解copy上来看一眼吧……
首先可以发现，画取最大美丽值时，每个格子的美丽值就是这 k个已知格子带来的限制(权值+距离*d)的最小值。
无解当且仅当一个已知格子的值不满足另一个已知格子带来的限制，因为否则用上面所说的赋值可以得到一组解。
过这k个格子的每个格子画一条横着的线和竖着的线，形成一个不超过k*k的大网格，每个小网格的格子要么在大网格的边上(两点之间)，要么在格子里(四点之间)。 先跑一遍最短路求出大网格上每个点的美丽值，同时判断是否有解。
边的贡献很好算(实际上也可以转化为格子)，下面考虑对大网格每个格子计算贡献。
对于这个格子里的点，它要考虑的限制从原来的k个点变成了4个点。
考虑对这4个点中的每个点计算贡献,先考虑有哪些点是由它的限制取到的最小值(当有多个点的限制同时取到最小值时，强制归为编号最小的那个点)，发现只用对一条横着的线，一条竖着的线，一条斜着的线求交。可以 分类讨论，更方便的方法是差分成三个三角形。
时间复杂度O(k^2logk)
std:
#include<bits/stdc++.h> using namespace std; template <typename T> void chmin(T &x,const T &y) { if(x>y)x=y; } typedef long long s64; #define rep(i,l,r) for(int i=l;i<=r;++i) const int K=500+5,D=1e9+7; s64 mi(s64 x,int y=D-2) { s64 ans=1; while(y) { if(y&1)ans=ans*x%D; x=x*x%D;y>>=1; } return ans; } const int niv_6=mi(6); int n,m,k,d; s64 g[K][K]; int q[2][K]; struct Point { int x,y;s64 v; }; bool operator >(const Point &a,const Point &b) { return a.v<b.v; } bool operator <(const Point &a,const Point &b) { return b>a; } Point p[K]; priority_queue<Point>heap; void push(const Point &p) { if(g[p.x][p.y]>p.v) { g[p.x][p.y]=p.v; heap.push(p); } } void push(int x,int y,const s64 &v) { push((Point){x,y,v}); } int check(s64 x,s64 y,int l,bool t) { int i=(y-x+s64(l)*d)/(2*d); return min(l-1,max(0,i-(t&&(x+s64(i)*d==y+s64(l-i)*d)))); } s64 S2(s64 a,s64 x) { a+=d; return (x*(x+1)/2%D*(a%D)+x*(x+1)%D*(2*x+1)%D*niv_6%D*d)%D; } s64 check_rec(s64 a,s64 b,s64 c,s64 d,int n,int m) { auto S=[&](s64 a,s64 b,s64 c,s64 d,bool tb,bool tc,bool td)->s64 { int xb=check(a,b,m,tb),xd=check(a,d,n,td),xc=check(a,c,n+m,tc); chmin(xc,xb+xd); --xc; chmin(xb,xc); chmin(xd,xc); return (S2(a,xc)-S2(a+s64(xd)*::d,xc-xd)-S2(a+s64(xb)*::d,xc-xb))%D; }; return (S(a,b,c,d,0,0,0)+S(b,a,d,c,1,0,0)+S(c,d,a,b,0,1,1)+S(d,c,b,a,1,1,1))%D; } s64 check_line(s64 x,s64 y,int l) { return check_rec(x-d,y-d,y-d,x-d,2,l); } int main() { freopen("painting.in","r",stdin);freopen("painting.out","w",stdout); scanf("%d%d%d%d",&n,&m,&k,&d); *q[0]=2;q[0][1]=0;q[0][2]=n+1; *q[1]=2;q[1][1]=0;q[1][2]=m+1; rep(i,1,k) { int x,y,v; scanf("%d%d%d",&x,&y,&v); p[i]=(Point){x,y,v}; q[0][++*q[0]]=x; q[1][++*q[1]]=y; } rep(o,0,1) { sort(q[o]+1,q[o]+*q[o]+1); *q[o]=unique(q[o]+1,q[o]+*q[o]+1)-q[o]-1; } rep(i,1,k) { Point &p=::p[i]; p.x=lower_bound(q[0]+1,q[0]+*q[0]+1,p.x)-q[0]; p.y=lower_bound(q[1]+1,q[1]+*q[1]+1,p.y)-q[1]; } rep(i,1,*q[0]) rep(j,1,*q[1])g[i][j]=4e18; rep(i,1,k)push(p[i]); while(!heap.empty()) { Point p=heap.top();heap.pop(); int x=p.x,y=p.y;s64 v=p.v; if(g[x][y]!=v)continue; if(x>1)push(x-1,y,v+s64(q[0][x]-q[0][x-1])*d); if(x<*q[0])push(x+1,y,v+s64(q[0][x+1]-q[0][x])*d); if(y>1)push(x,y-1,v+s64(q[1][y]-q[1][y-1])*d); if(y<*q[1])push(x,y+1,v+s64(q[1][y+1]-q[1][y])*d); } bool impo=0; rep(i,1,k) { Point p=::p[i]; if(g[p.x][p.y]!=p.v){impo=1;break;} } if(impo){puts("IMPOSSIBLE");exit(0);} s64 ans=0; rep(i,2,*q[0]-1) rep(j,2,*q[1]-1)(ans+=g[i][j])%=D; rep(i,2,*q[0]-1) rep(j,1,*q[1]-1)(ans+=check_line(g[i][j],g[i][j+1],q[1][j+1]-q[1][j]))%=D; rep(i,1,*q[0]-1) rep(j,2,*q[1]-1)(ans+=check_line(g[i][j],g[i+1][j],q[0][i+1]-q[0][i]))%=D; rep(i,1,*q[0]-1) rep(j,1,*q[1]-1) (ans+=check_rec(g[i][j],g[i][j+1],g[i+1][j+1],g[i+1][j],q[0][i+1]-q[0][i],q[1][j+1]-q[1][j]))%=D; printf("%d ",int((ans+D)%D)); }
今日还有一些诡异的插曲……
自己打T3暴力打完之后突然ZZ，然后把机房后面那条语句打了上去。看到sudo is now world writeable的时候内心很崩溃orz，然后继续作死把权限改成000之后想cd ～，看到permission denied更绝望……
然后只好调回777将就着用，幸好机房电脑能还原不然可就凉凉了。