（AtCoder Beginner Contest 315）

A.直接模拟即可

import random
import sys
import os
import math
from collections import Counter, defaultdict, deque
from functools import lru_cache, reduce
from itertools import accumulate, combinations, permutations
from heapq import nsmallest, nlargest, heapify, heappop, heappush
from io import BytesIO, IOBase
from copy import deepcopy
import threading
import bisectBUFSIZE = 4096class FastIO(IOBase):newlines = 0def __init__(self, file):self._fd = file.fileno()self.buffer = BytesIO()self.writable = "x" in file.mode or "r" not in file.modeself.write = self.buffer.write if self.writable else Nonedef read(self):while True:b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))if not b:breakptr = self.buffer.tell()self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)self.newlines = 0return self.buffer.read()def readline(self):while self.newlines == 0:b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))self.newlines = b.count(b"\n") + (not b)ptr = self.buffer.tell()self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)self.newlines -= 1return self.buffer.readline()def flush(self):if self.writable:os.write(self._fd, self.buffer.getvalue())self.buffer.truncate(0), self.buffer.seek(0)class IOWrapper(IOBase):def __init__(self, file):self.buffer = FastIO(file)self.flush = self.buffer.flushself.writable = self.buffer.writableself.write = lambda s: self.buffer.write(s.encode("ascii"))self.read = lambda: self.buffer.read().decode("ascii")self.readline = lambda: self.buffer.readline().decode("ascii")sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")def I():return input()def II():return int(input())def MI():return map(int, input().split())def LI():return list(input().split())def LII():return list(map(int, input().split()))def GMI():return map(lambda x: int(x) - 1, input().split())def LGMI():return list(map(lambda x: int(x) - 1, input().split()))def solve():s=I()res=""for i in s:if i not in "aeiou":res+=iprint(res)if __name__ == '__main__':for _ in range(1):solve()

B.模拟

import random
import sys
import os
import math
from collections import Counter, defaultdict, deque
from functools import lru_cache, reduce
from itertools import accumulate, combinations, permutations
from heapq import nsmallest, nlargest, heapify, heappop, heappush
from io import BytesIO, IOBase
from copy import deepcopy
import threading
import bisectBUFSIZE = 4096class FastIO(IOBase):newlines = 0def __init__(self, file):self._fd = file.fileno()self.buffer = BytesIO()self.writable = "x" in file.mode or "r" not in file.modeself.write = self.buffer.write if self.writable else Nonedef read(self):while True:b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))if not b:breakptr = self.buffer.tell()self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)self.newlines = 0return self.buffer.read()def readline(self):while self.newlines == 0:b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))self.newlines = b.count(b"\n") + (not b)ptr = self.buffer.tell()self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)self.newlines -= 1return self.buffer.readline()def flush(self):if self.writable:os.write(self._fd, self.buffer.getvalue())self.buffer.truncate(0), self.buffer.seek(0)class IOWrapper(IOBase):def __init__(self, file):self.buffer = FastIO(file)self.flush = self.buffer.flushself.writable = self.buffer.writableself.write = lambda s: self.buffer.write(s.encode("ascii"))self.read = lambda: self.buffer.read().decode("ascii")self.readline = lambda: self.buffer.readline().decode("ascii")sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")def I():return input()def II():return int(input())def MI():return map(int, input().split())def LI():return list(input().split())def LII():return list(map(int, input().split()))def GMI():return map(lambda x: int(x) - 1, input().split())def LGMI():return list(map(lambda x: int(x) - 1, input().split()))def solve():n=II()a=[0]+LII()s=sum(a)s=(s+1)//2for i in range(1,n+1):if s>a[i]:s-=a[i]else:print(i,end=" ")print(s)breakif __name__ == '__main__':for _ in range(1):solve()

C.维护一个不等于当前b[i][0]的的前面最大值的a[i][1]

如果相等就顺便维护一个前面的最大的a[i][1]

#include<bits/stdc++.h>
using namespace std;
const int N = 5e6+10;
#define int long long
int n,m;
void solve(){cin>>n;vector<array<int,2>> a(n+1);int res=0;for(int i=1;i<=n;i++){cin>>a[i][0]>>a[i][1];//  res=max(res,a[i][1]+a[i][1]/2);}sort(a.begin()+1,a.end());int now=0;int idx=1;for(int i=2;i<=n;i++){while(idx<i&&a[idx][0]!=a[i][0]){now=max(now,a[idx][1]);idx++;}if(a[i][0]==a[i-1][0]){res=max({res,a[i][1]+a[i-1][1]/2,a[i][1]+now});}else res=max(res,a[i][1]+now);if(a[i][0]==a[i-1][0]) a[i][1]=max(a[i-1][1],a[i][1]);}cout<<res;
}
signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;//cin>>t;while(t--) solve();return 0;
}

D.

每次删除一行或一列，最多进行n+m次操作，所以直接暴力枚举即可

统计每一行26个字母的个数，顺便动态维护一下当前还剩下的行和列即可

#include<bits/stdc++.h>
using namespace std;
const int N =2010+10;int n,m;
char g[N][N];
int row[N][30],col[N][30];
signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)cin>>g[i][j];}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){row[i][g[i][j]-'a']++;col[j][g[i][j]-'a']++;}}vector<bool> fx(n+10,false),fy(m+10,false);int r=n,c=m;for(int k=1;k<=n+m;k++){vector<pair<int,int>> a,b;for(int i=1;i<=n;i++){if(fx[i]) continue;for(int j=0;j<26;j++){if(row[i][j]==c&&c>1){a.emplace_back(i,j);}}}for(int i=1;i<=m;i++){if(fy[i]) continue;for(int j=0;j<26;j++){if(col[i][j]==r&&r>1)b.emplace_back(i,j);}}for(auto [x,y]:a){fx[x]=true;for(int i=1;i<=m;i++)col[i][y]--;r--;}for(auto [x,y]:b){fy[x]=true;for(int i=1;i<=n;i++)row[i][y]--;c--;}}cout<<r*c<<"\n";
}

E.

首先一眼topsort,但是有其他无用点干扰，所以第一次bfs直接找到需要用的点，再从需要用的点拓扑排序一次即可，求一个dfs的后序遍历也行，

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
#define int long long
int n,m;
vector<int> g[N],rg[N];
int d[N],rd[N];
bool st[N];
void solve(){cin>>n;for(int i=1;i<=n;i++){int cnt;cin>>cnt;for(int j=1;j<=cnt;j++){int a;cin>>a;g[i].push_back(a);d[a]++;rg[a].push_back(i);rd[i]++;}}queue<int> q;q.push(1);st[1]=true;while(q.size()){auto t=q.front();q.pop();for(auto v:g[t]){if(!st[v]){st[v]=true;q.push(v);}}}while(q.size()) q.pop();vector<int> res;for(int i=1;i<=n;i++){if(rd[i]==0&&st[i]){q.push(i);}}//  vector<int> res;while(q.size()){auto t=q.front();q.pop();if(t==1)break;// if(!st[t]) continue;res.push_back(t);for(auto v:rg[t]){if(--rd[v]==0&&st[v]) q.push(v);}}for(auto x:res)cout<<x<<" ";
}
signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;//cin>>t;while(t--) solve();return 0;
}

F.

答案最大是1e4*1e4左右把，大概就是0走到1e4再走到0再走到1e4,

c>30就大过这个了，所以不如全走，

所以我们只需要维护跳过30个点即可，

dp方程就是走了前i个点，已经跳过了j个点，需要走的最小距离，且当前点必走

#include<bits/stdc++.h>
using namespace std;
const int N = 10010+10;int n,m;
int x[N],y[N];
double f[N][50];double get(int x1,int y1,int x2,int y2){return hypot(x1-x2,y1-y2);// return 1.0*((double)(sqrt((x1-x2)*(x1-x2)))+(double)(sqrt((y1-y2)*(y1-y2))));
}
signed main(){//  cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);cin>>n;for(int i=1;i<=n;i++) cin>>x[i]>>y[i];memset(f,99,sizeof(f));f[1][0]=0;for(int i=2;i<=n;i++){for(int j=0;j<=30;j++){for(int k=i-1;k>=max(1,i-j-1);k--){f[i][j]=min(f[i][j],f[k][j-(i-1-k)]+get(x[i],y[i],x[k],y[k]));}}}double p=1.0,res=1e100;for(int i=1;i<=30;i++) f[n][i]+=p,p*=2.0;for(int i=0;i<=30;i++) res=min(res,f[n][i]);printf("%.10lf",res);
}

G.我们让系数可以为0，因为方便求exgcd

就直接N--，X-=A+B+C，就A,B,C系数至少为1，直接一开始去掉这个1即可，然后注释都在代码里

​
#include<bits/stdc++.h>
using namespace std;
#define int long long
int exgcd(int a, int b, int &x, int &y)  // 扩展欧几里得算法, 求x, y，使得ax + by = gcd(a, b)
{if (!b){x = 1; y = 0;return a;}int d = exgcd(b, a % b, y, x);y -= (a / b) * x;return d;
}int N,A,B,C,X;
signed main(){ios::sync_with_stdio(false);cin>>N>>A>>B>>C>>X;N--,X-=A+B+C; if(X<0){puts("0");return 0;}int x0,y0;//x0*B+y0*C=gcd(B,C)int d=exgcd(B,C,x0,y0),b=B/d,c=C/d,ans=0;//k0=b,k1=cx0=(x0%c+c)%c;y0=(d-B*x0)/C;//求出x0为最小非负数解法的for(int i=0;i<=N;i++){int x=X-i*A;//求 x1*B+y1*C=x,区间连续，所以求x1的合法最小值和最大值if(x%d!=0)continue;if(x<0)break;//x是d的倍数//求 x1*B+y1*C=x/dint l,r,x1=x/d%c*x0,y1;//同理求出x1为最小非负数解法的，和当前y1x1=(x1%c+c)%c,y1=(x-x1*B)/C;//x1的最小值取决于y1，因为现在x1是最小非负数了//所以现在要看y1的合法情况了，就是找y1<=N的最小系数//其实可以想象现在的x1虽然是最小的，但是y1可能大于N//这是不合法的，所以我们要把y1约束到N里面，所以现在只能把x1增大l=max(0ll,(y1-N+b-1ll)/b);if(x1>N||y1<0)r=-1ll;else r=min((N-x1)/c,y1/b);//右边界直接把y1变小或者单纯把x1变大if(l<=r)ans+=r-l+1;}cout<<ans;
}​