外面吵得风生水起，我校平静地在打比赛，丝毫不知道这次比赛的题目就是把2018银川邀请赛的题照搬过来了QAQ，主办方真牛逼。。
A Maximum（思维）
题意：维护一个栈，支持入栈和出栈操作，并计算每次操作后的栈中最大值，得到最终结果。
思路：
这题真的是，我和hxc轮流做这道题，被坑惨了，一直以为使用数据结构来做，没想到点上去。思维题，每次保证栈顶为栈中最大元素。如果当前入栈的元素为x，当前栈顶元素为y，如果x>=y，这个没问题，直接入栈就行了; 如果x<y，我们相当于直接用y替换x，再入栈即可。
吸取教训，这种过的人很多的，不要想复杂，怎么简单怎么来。
AC代码：
#include<cstdio> #include<algorithm> #include<set> #include<map> using namespace std; const int maxn=5e6+5; typedef unsigned int UI; int T,cas,top; UI stk[maxn]; long long ans; int n,p,q,m; unsigned int SA,SB,SC; unsigned int rng61(){ SA^=SA<<16; SA^=SA>>5; SA^=SA<<1; unsigned int t=SA; SA=SB; SB=SC; SC^=t^SA; return SC; } void gen(){ scanf("%d%d%d%d%u%u%u",&n,&p,&q,&m,&SA,&SB,&SC); for(int i=1;i<=n;++i){ if(rng61()%(p+q)<p){ stk[++top]=rng61()%m+1; stk[top]=max(stk[top-1],stk[top]); } else if(top>0) --top; ans^=1LL*i*stk[top]; } } int main(){ scanf("%d",&T); while(T--){ ans=0; top=0; gen(); printf("Case #%d: %lld ",++cas,ans); } return 0; }
B. Rolling The Polygon
hxc写得。
AC代码：
#pragma GCC optimize(2) #include <cstdio> #include <queue> #include <string> #include <cstring> #include <algorithm> #include <cstdlib> #include <iostream> #include <iomanip> #include <cmath> #include <vector> #include <set> #include <map> #include <fstream> #include <cassert> #define ll long long #define R register int #define I inline void #define lc c[x][0] #define rc c[x][1] using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 100; struct node { double x,y; }pp[maxn],qq; double rad(node a,node b,node c) { return acos(((a.x - b.x) * (c.x - b.x) + (a.y - b.y) * (c.y - b.y)) / sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)) / sqrt((c.x - b.x) * (c.x - b.x) + (c.y - b.y) * (c.y - b.y))); } int t,n; int main() { scanf("%d",&t); int o = t; while(t--) { double ans = 0; scanf("%d",&n); for(int i = 1; i <= n; i++) scanf("%lf%lf",&pp[i].x,&pp[i].y); scanf("%lf%lf",&qq.x,&qq.y); for(int i = 1; i <= n; i++) { //printf("%qwe%lf ",rad(pp[(i - 2 + n * 2) % n + 1],pp[i],pp[i % n + 1])); double temp = sqrt((qq.x - pp[i].x) * (qq.x - pp[i].x) + (qq.y - pp[i].y) * (qq.y - pp[i].y)); ans += temp * (M_PI - rad(pp[(i - 2 + n * 2) % n + 1],pp[i],pp[i % n + 1])); } printf("Case #%d: %.3lf ",o - t,ans); } }
C. Ceasar Cipher （水题，模拟就行了）
AC代码：
#include<cstdio> #include<algorithm> using namespace std; int T,n,m,cas,num; char s1[55],s2[55],s3[55]; int main(){ scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); scanf("%s%s%s",s1,s2,s3); num=(s1[0]-s2[0]+26)%26; printf("Case #%d: ",++cas); for(int i=0;i<m;++i) printf("%c",(s3[i]-'A'+num)%26+'A'); printf(" "); } return 0; }
D. Moving On （概率）
题意：
第一问：n个人对应n个座位，按1~n的顺序选择，1号任意选，i号选i(如果i未选)或任意选(如果i已选)，i>=2，求最后一个选的人选对的概率。
第二问：m个人对应m个座位，按任意次序选择(m!种排列)，1号任意选，i号选i(如果i未选)或任意选(如果i已选)，i>=2，求最后一个选的人选对的概率。
思路：
第一问dfs打表发现概率为0.5，第二种情况对于m!种排列：
如果1在最后选，那么一定能选对，概率为1，有(m-1)!种。
如果1不在最后，1前面的一定能选对，从1开始往后的就变成第1问，概率为0.5，有m!-(m-1)!种。
故第二种概率为(m-1)!/m!*1+(m!-(m-1)!)/m!*0.5=(m+1)/(2*m)。
刚开始算错了，卡了两小时QAQ。。
AC代码：
#include<cstdio> #include<algorithm> using namespace std; int T,n,m,cas; int main(){ scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); printf("Case #%d: ",++cas); if(n==1) printf("1.000000 "); else printf("0.500000 "); printf("%.6f ",1.0*(m+1)/(2.0*m)); } return 0; }
F. Moving On（floyd变形）
题意：给定一个图，每个点有个权值r[i]，多次询问，每次询问u到v的最短路，且该最短路不经过权值大于w的点。
思路：按权值进行排序，然后floyd，dp[k][i][j]表示经过排序后的前k个点i到j的最短路。询问的时候二分查找即可。但是这题似乎卡常，我定义数组dp[i][j][k]会T,而dp[k][i][j]就A了。绝望-_-。。
AC代码：
#include<cstdio> #include<algorithm> using namespace std; const int maxn=205; const int inf=0x3f3f3f3f; int T,cas,n,m; int u,v,w,dp[maxn][maxn][maxn]; struct node{ int val,id; }a[maxn]; bool operator < (const node& x,const node& y){ return x.val<y.val; } int main(){ scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); for(int i=1;i<=n;++i){ scanf("%d",&a[i].val); a[i].id=i; } for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) scanf("%d",&dp[0][i][j]); sort(a+1,a+n+1); for(int k=1;k<=n;++k) for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) dp[k][i][j]=min(dp[k-1][i][j],dp[k-1][i][a[k].id]+dp[k-1][a[k].id][j]); printf("Case #%d: ",++cas); while(m--){ scanf("%d%d%d",&u,&v,&w); int l=1,r=n,mid; while(l<=r){ mid=(l+r)>>1; if(a[mid].val<=w) l=mid+1; else r=mid-1; } printf("%d ",dp[r][u][v]); } } return 0; }