题目链接：点击打开链接
说明：前五题简单题就不写了。。。
F：这是裸nlogn的求最长上升序列算法，前后各求一下取小就行了。
#include<iostream> #include<algorithm> #include<stdio.h> #include<string.h> #include<queue> using namespace std; typedef long long ll; const int mx = 5e5+10,mod = 1e9+7; int n,m; int fron[mx],back[mx],a[mx],b[mx]; int main(){ fron[0]=0; while(~scanf("%d",&n)){ for(int i=0;i<n;i++) scanf("%d",a+i); int len=1; b[0] = a[0]; for(int i=1;i<n;i++){ int k = lower_bound(b,b+len,a[i])-b; if(k==len) len++; b[k]=a[i], fron[i]=k; } len = 1, back[n-1] = 0; b[0] = a[n-1]; for(int i=n-2;i>=0;i--){ int k = lower_bound(b,b+len,a[i])-b; if(k==len) len++; b[k]=a[i], back[i]=k; } int ans = 0; for(int i=0;i<n;i++) ans = max(ans,min(fron[i],back[i])*2+1); printf("%d\n",ans); } return 0; }G：贪心思路。按攻击力从大到下排序，相同的按血量从小到大排序。然后比较。 #include<iostream> #include<algorithm> #include<stdio.h> #include<string.h> #include<queue> #include<set> #define inf 0x3f3f3f3f using namespace std; typedef long long ll; const int mx = 20; int n,m; struct data{ int v,a; data(){} data(int vv,int aa){ v = vv, a = aa ; } bool operator < (data A)const{ if(a==A.a) return v<A.v; return a>A.a; } }s[mx],q[mx]; int main(){ int t; scanf("%d",&t); while(t--){ scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d%d",&s[i].v,&s[i].a); for(int i=0;i<n;i++) scanf("%d%d",&q[i].v,&q[i].a); sort(q,q+n); int j = 0, k = 0; while(j<n&&k<n){ int vj = (q[k].v-1)/s[j].a+1, vk = (s[j].v-1)/q[k].a+1; if( vj < vk ) s[j].v -= vj*q[k].a, k++; else if( vj > vk ) q[k].v -= vk*s[j].a, j++; else j++ ,k++; } puts(k==n? "NO":"YES"); } return 0; }H：考虑到n才2w，直接用vector全部存入容器中，直接暴力。 #include<iostream> #include<algorithm> #include<stdio.h> #include<string.h> #include<queue> #include<set> #include<vector> #define inf 0x3f3f3f3f using namespace std; typedef long long ll; const int mx = 2e4+10; int n,m,a[mx]; vector <int> st[mx/2]; int main(){ int t; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&m); for(int i=0;i<n;i++) scanf("%d",a+i); for(int i=0;i<=n/2;i++) st[i].clear(); for(int i=1;i<=n/2;i++){ int j = 0; while(j*i<n){ st[i].push_back(a[j*i]); j++; } sort(st[i].begin(),st[i].end()); } while(m--){ int x,y; scanf("%d%d",&x,&y); if(x>n/2&&x<n){ if(y==1) printf("%d\n",max(a[x],a[0])); else if(y==2) printf("%d\n",min(a[x],a[0])); else puts("-1"); } else if(x>=n) printf("%d\n",y==1? a[0]:-1); else printf("%d\n",y>st[x].size()? -1:st[x][st[x].size()-y]); } }I：动态规划面积从小到大，已知n<=2&&m<=2的棋盘必为必败态，然后规划每个点是否能进入至少一个必败态，则其就是必胜态，反之必败。
#include<iostream> #include<algorithm> #include<stdio.h> #include<string.h> #include<queue> #include<set> #include<vector> #define inf 0x3f3f3f3f using namespace std; typedef long long ll; const int mx = 5e2+100; int n,m,pri[mx],top; bool vis[mx],vic[mx][mx]; void init(){ for(int i=2;i<mx;i++){ if(!vis[i]) pri[top++] = i; for(int j=0;j<top&&pri[j]*i<mx;j++){ vis[pri[j]*i] = 1; if(i%pri[j]==0) break; } } } int main(){ int t,top = 0; init(); memset(vic,0,sizeof(vic)); for(int i=1;i<=500;i++){ for(int j=1;j<=500;j++){ if(i<=2&&j<=2) continue; int k = 0; while(!vic[i][j]&&pri[k]<i){ if(!vic[i-pri[k]][j]) vic[i][j] = 1; k++; } k = 0; while(!vic[i][j]&&pri[k]<j){ if(!vic[i][j-pri[k]]) vic[i][j] = 1; k++; } k = 0; while(!vic[i][j]&&pri[k]<j&&pri[k]<i){ if(!vic[i-pri[k]][j-pri[k]]) vic[i][j] = 1; k++; } } } scanf("%d",&t); while(t--){ scanf("%d%d",&n,&m); puts(vic[n][m]? "Sora":"Shiro"); } return 0; }J：代码丢了（不想写了。。。）简单说你会发现要是没有233的限制，那么每个n累加的值应该是（n*n+n）/2,那么用这个值减去i的1-232和后面的n-232到n就是答案了。这两个分别用到O（n）的求1-n的欧拉函数和O（sqrt(n)）的求1-n的欧拉函数。K：二分求答案
#include<iostream> #include<algorithm> #include<stdio.h> #include<string.h> #include<queue> #include<set> #define inf 0x3f3f3f3f using namespace std; typedef long long ll; const int mx = 1e5+10; int n,m; struct data{ int ai,bi; }s[mx]; bool cmp_1(data A,data B){ if(A.bi==B.bi) return A.ai>B.ai; return A.bi<B.bi; } bool check(int x,int si){ int sum = 0, cnt = 0; for(int i=0;i<n;i++){ if(s[i].ai>=x){ cnt++; sum += s[i].bi; } if(cnt==si) break; } return cnt==si&&sum<=m; } int main(){ int t; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&m); for(int i=0;i<n;i++) scanf("%d%d",&s[i].ai,&s[i].bi); sort(s,s+n,cmp_1); int top = 0,sum = m; while(top<n&&sum>=s[top].bi){ sum -= s[top].bi; top++; } int l = 1,r = 1e4; while(l<=r){ int mid = (l+r)>>1; if(check(mid,top)) l = mid+1; else r = mid-1; } printf("%d %d\n",top,r); } return 0; } M：线段树维护一个点增加最多的值和减少最多的值。当然用到了懒人思想。 #include<iostream> #include<algorithm> #include<stdio.h> #include<string.h> #include<queue> #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define inf 0x3f3f3f3f using namespace std; typedef long long ll; const int mx = 1e5+10,mod = 1e9+7; int n,m,num[mx<<2],q,a[mx]; int just[mx<<2],nage[mx<<2]; struct data{ int MAX,MIN; data(){} data(int maxx,int minn){ MIN = minn, MAX = maxx ; } }; void Splite(int rt){ just[rt<<1] = max(just[rt<<1],num[rt<<1]+just[rt]); just[rt<<1|1] = max(just[rt<<1|1],num[rt<<1|1]+just[rt]);; nage[rt<<1] = min(nage[rt<<1],num[rt<<1]+nage[rt]); nage[rt<<1|1] = min(nage[rt<<1|1],num[rt<<1|1]+nage[rt]); num[rt<<1] += num[rt]; num[rt<<1|1] += num[rt]; just[rt] = nage[rt] = num[rt] = 0; } void update(int L,int R,int l,int r,int rt,int v){ if(L<=l&&R>=r){ num[rt]+=v; just[rt] = max(just[rt],num[rt]); nage[rt] = min(nage[rt],num[rt]); return ; } if(num[rt]||just[rt]||nage[rt]) Splite(rt); int mid = (l+r)>>1; if(L<=mid) update(L,R,lson,v); if(R>mid) update(L,R,rson,v); } data query(int L,int l,int r,int rt){ if(l==r) return data(just[rt],nage[rt]); if(just[rt]||nage[rt]||num[rt]) Splite(rt); int mid = (l+r)>>1; if(L<=mid) return query(L,lson); return query(L,rson); } int main(){ int t; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&q); for(int i=1;i<=n;i++) scanf("%d",a+i); memset(num,0,sizeof(num)); memset(just,0,sizeof(just)); memset(nage,0,sizeof(nage)); while(q--){ int d; scanf("%d",&d); if(d==1){ int x,y,z; scanf("%d%d%d",&x,&y,&z); update(x,y,1,n,1,z); }else{ scanf("%d",&d); data t = query(d,1,n,1); printf("%d\n",max(abs(a[d]+t.MAX),abs(a[d]+t.MIN))); } } } return 0; }O： 题目告诉我们当然主人公够聪明，但是不知道传送门是怎么对应的，那么此时可以看做只有两个操作。一：不进入传送门直接走。二：进入离出发点最近的传送门(毕竟不知道肯定是选择最近的啊)。然后用一个bfs套dfs将传送门出口作为新的出发点，看看是否能到达终点，若有一种不能则为-1.#include<iostream> #include<algorithm> #include<stdio.h> #include<string.h> #include<queue> #define inf 0x3f3f3f3f using namespace std; typedef long long ll; const int mx = 1e2+10,co[4][2]={1,0,0,1,-1,0,0,-1}; int n,m,cnt1,ans; char map[mx][mx]; struct node{ int x,y,k; node(){} node(int xx,int yy,int kk){ x = xx, y = yy, k = kk; } }a[5],b[5]; bool vis2[5]; int bfs(int beg,int eng){ queue<node> skt; bool vis[mx][mx],flag = 0; int sum = inf; memset(vis,0,sizeof(vis)); skt.push(node(beg,eng,0)); vis[beg][eng]=1; while(!skt.empty()){ node no = skt.front(); skt.pop(); for(int i=0;i<4;i++){ node po = node(no.x+co[i][0],no.y+co[i][1],no.k+1); if(po.x<0||po.y<0||po.x>=n||po.y>=m) continue; if(vis[po.x][po.y]||map[po.x][po.y]=='#') continue; vis[po.x][po.y] = 1; if(map[po.x][po.y]=='T') return min(sum,po.k); if(!flag&&map[po.x][po.y]=='i'){ map[po.x][po.y] = '.'; for(int j=0;j<cnt1;j++){ if(vis2[j]) continue; vis2[j] = 1; if(sum==inf) sum = bfs(b[j].x,b[j].y)+po.k+1; else sum = max(sum,bfs(b[j].x,b[j].y)+po.k+1); vis2[j] = 0; } map[po.x][po.y] = 'i'; flag = 1; } skt.push(po); } } return sum; } int main(){ int t,beg,eng; scanf("%d",&t); while(t--){ ans = 0, cnt1 = 0; scanf("%d%d",&n,&m); for(int i=0;i<n;i++){ scanf("%s",map[i]); for(int j=0;j<m;j++){ if(map[i][j]=='S') beg = i, eng = j; else if(map[i][j]=='o') b[cnt1++]=node(i,j,0); } } ans = bfs(beg,eng); printf("%d\n",ans>=inf? -1:ans); } return 0; }
