吐槽：只能说是上分好场，可惜没打，唉
A：Beru-taxi （水题，取最小值）
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <stdlib.h> using namespace std; typedef long long LL; int main(){ double x,y,ret=1e9,a,b,v; int n; scanf("%lf%lf%d",&x,&y,&n); for(int i=0;i<n;++i){ scanf("%lf%lf%lf",&a,&b,&v); ret=min(ret,sqrt((x-a)*(x-a)+(y-b)*(y-b))/v); } printf("%.10f ",ret); return 0; }
B: Interesting drink(二分下)
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <stdlib.h> using namespace std; typedef long long LL; const int N = 1e5+5; int a[N],n,m,q; int main(){ scanf("%d",&n); for(int i=1;i<=n;++i)scanf("%d",&a[i]); sort(a+1,a+1+n); scanf("%d",&q); while(q--){ scanf("%d",&m); printf("%d ",upper_bound(a+1,a+1+n,m)-a-1); } return 0; }
C：Hard problem（简单的O(n)dp,dp[i][0/1]代表不反转或者反转,随便写写）
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <stdlib.h> using namespace std; typedef long long LL; const int N = 1e5+5; const int INF = 0x3f3f3f3f; LL dp[N][2]; int c[N],n; string a[N],b[N]; int main(){ scanf("%d",&n); for(int i=1;i<=n;++i)scanf("%d",&c[i]); for(int i=1;i<=n;++i){ cin>>a[i];b[i]=a[i]; reverse(b[i].begin(),b[i].end()); } memset(dp,-1,sizeof(dp)); dp[1][1]=c[1];dp[1][0]=0; for(int i=2;i<=n;++i){ if(a[i]>=a[i-1]&&dp[i-1][0]!=-1) dp[i][0]=dp[i-1][0]; if(a[i]>=b[i-1]&&dp[i-1][1]!=-1){ if(dp[i][0]==-1)dp[i][0]=dp[i-1][1]; else dp[i][0]=min(dp[i][0],dp[i-1][1]); } if(b[i]>=a[i-1]&&dp[i-1][0]!=-1) dp[i][1]=dp[i-1][0]+c[i]; if(b[i]>=b[i-1]&&dp[i-1][1]!=-1){ if(dp[i][1]==-1)dp[i][1]=dp[i-1][1]+c[i]; else dp[i][1]=min(dp[i][1],dp[i-1][1]+c[i]); } if(dp[i][0]==-1&&dp[i][1]==-1){ printf("-1 ");return 0; } } int i=n; if(dp[i][0]!=-1&&dp[i][1]==-1)printf("%I64d ",dp[i][0]); else if(dp[i][1]!=-1&&dp[i][0]==-1)printf("%I64d ",dp[i][1]); else printf("%I64d ",min(dp[i][0],dp[i][1])); return 0; }
D：Vasiliy's Multiset(老题了，01字典树贪心)
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <stdlib.h> using namespace std; typedef long long LL; const int N = (2e5)*30; const int INF = 0x3f3f3f3f; int ch[N][2],cnt[N],tot,n; int newnode(){ ++tot;memset(ch[tot],-1,sizeof(ch[tot]));return tot; } void add(int x,int t){ int now=0; for(int i=29;i>=0;--i){ int nx=(x&(1<<i))?1:0; if(ch[now][nx]==-1)ch[now][nx]=newnode(); now=ch[now][nx];cnt[now]+=t; } } int ask(int x){ int now=0,ret=0; for(int i=29;i>=0;--i){ int nx=(x&(1<<i))?1:0; if(ch[now][nx^1]!=-1&&cnt[ch[now][nx^1]]){ now=ch[now][nx^1];ret+=(1<<i); } else now=ch[now][nx]; } return ret; } char op[5]; int main(){ tot=-1;newnode();add(0,1); scanf("%d",&n); while(n--){ int x;scanf("%s%d",op,&x); if(op[0]=='+')add(x,1); else if(op[0]=='-')add(x,-1); else printf("%d ",ask(x)); } return 0; }
E:Working routine（十字链表暴力，如果不会的话，可以去看看dance link的实现）
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <stdlib.h> using namespace std; typedef long long LL; const int N = 1e3+5; struct Node{ int u,d,l,r,v; }p[N*N]; int cnt,n,m,q,mp[N][N]; int main(){ cnt=-1; scanf("%d%d%d",&n,&m,&q); for(int i=1;i<=n;++i){ mp[i][0]=++cnt; } for(int i=1;i<=m;++i)mp[0][i]=++cnt; for(int i=1;i<=n;++i){ for(int j=1;j<=m;++j){ ++cnt;scanf("%d",&p[cnt].v); mp[i][j]=cnt; } } for(int i=1;i<=n;++i){ for(int j=1;j<=m;++j){ int id=mp[i][j]; p[id].l=mp[i][j-1]; p[id].r=mp[i][(j+1)%(m+1)]; p[id].u=mp[i-1][j]; p[id].d=mp[(i+1)%(n+1)][j]; } } for(int i=1;i<=n;++i){ p[mp[i][0]].l=mp[i][m]; p[mp[i][0]].r=mp[i][1]; } for(int j=1;j<=m;++j){ p[mp[0][j]].u=mp[n][j]; p[mp[0][j]].d=mp[1][j]; } while(q--){ int x1,y1,x2,y2,h,w; scanf("%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&h,&w); int now1=mp[x1][0],now2=mp[x2][0],k1,k2; for(int i=1;i<=y1;++i)now1=p[now1].r; for(int i=1;i<=y2;++i)now2=p[now2].r; k1=now1,k2=now2; for(int i=1;i<=w;++i){ swap(p[p[k1].u].d,p[p[k2].u].d); swap(p[k1].u,p[k2].u); if(i==w)break; k1=p[k1].r;k2=p[k2].r; } for(int i=1;i<=h;++i){ swap(p[p[now1].l].r,p[p[now2].l].r); swap(p[now1].l,p[now2].l); swap(p[p[k1].r].l,p[p[k2].r].l); swap(p[k1].r,p[k2].r); if(i==h)break; now1=p[now1].d;now2=p[now2].d; k1=p[k1].d;k2=p[k2].d; } for(int i=1;i<=w;++i){ swap(p[p[now1].d].u,p[p[now2].d].u); swap(p[now1].d,p[now2].d); now1=p[now1].r;now2=p[now2].r; } } for(int i=1;i<=n;++i){ int id=p[mp[i][0]].r; for(int j=1;j<m;++j){ printf("%d ",p[id].v); id=p[id].r; } printf("%d ",p[id].v); } return 0; }