平均题目难度比较简单，签到题比较多
A题：Stoichiometry
高斯消元，不会。。
B题：Pokemon Go Go
我做出来的第一道状压dp题
#include<iostream> #include<algorithm> #include<map> using namespace std; const int INF = 1e9; const int MAXN = 1<<21; map<string,int> used; int ans = INF; int n, cnt = 0; struct MON{ int x,y; string name; }mon[24],order[24]; int ABS(int a){ if(a>=0) return a; return -a; } int dp[23][MAXN]; int dis[23][23]; int main() { cin>>n; for(int i =1;i<=n;i++){ cin>>mon[i].x>>mon[i].y>>mon[i].name; used[mon[i].name] = 1; } for(int i =1;i<=n;i++){ if(used[mon[i].name]==1) { used[mon[i].name] = 0; cnt++; } } mon[0].x = 0;mon[0].y = 0; for(int i = 0 ;i<=n;i++){ for(int j = 0;j<=n;j++){ dis[i][j] = ABS(mon[i].x-mon[j].x)+ABS(mon[i].y-mon[j].y); } } //for(int i =1;i<=n;i++) cout<<dis[0][i]<<endl; for(int i = 0;i<=n;i++){ for(int j = 0;j<(1<<(n+1));j++){ dp[i][j] = INF; if(j==0) dp[i][j] = 0; } } dp[0][1] = 0; for(int s = 1;s<(1<<(n+1));s+=2 ){ for(int i = 0 ;i<=n;i++){ if(s&(1<<i)){ for(int j = 0;j<=n;j++){ if(s&(1<<j)){ dp[i][s] = min(dp[i][s],dp[j][s^(1<<i)]+dis[i][j]); } } } } int ct = 0; bool flag = true; for(int i = 1;i<=n;i++){ if(!(s&(1<<i))) continue; if(!used[mon[i].name]) { used[mon[i].name] = 1; ct++; } else { flag = false; break; } } for(int i = 1;i<=n;i++) used[mon[i].name] = 0; if(flag&&ct==cnt){ for(int i = 1;i<=n;i++){ if(s&(1<<i)){ ans=min(ans,dp[i][s]+dis[0][i]); } } } } cout<<ans<<endl; return 0; }
C题：Urban Design
签到思维题，我比赛时过了这题
D题：Smooth Array
给一个 n 个元素的数组，修改其中几个数使得这个数组里所有的连续 k 个数的和都为 s ，求最少修改次数
刚开始写了个背包，没过样例，发现应该是分组背包，后来发现是要初始化为-INF的分组背包，然后又不会做了..
显然这n个数被分成了k类，第一类是下标模k为0的，第k类是下标模k为k-1的，同类的数都要等于同一个数
用a[i][j]表示第 i 类数里等于 j 的数的个数,可以当作第 i 类数选择都等于 j 时的贡献，贡献最大时，修改次数最少
那么就可以当作分组背包来算贡献，第 i 类数选择都等于 j ，那么其体积为 j ，价值为a[i][j]，容量为 s ，一共有 k 组背包，每组背包又有 s+1 个决策，复杂度O(k*s^2),会T
如果不把贡献为 0 的背包算进去，一共就只有 n 个背包，这样的话虽然时间复杂度低了，但又可能会出现这 n 个背包不能把体积用完的情况，所以有一组背包是要选择 原数组不存在的数的 背包（贡献为0），
这我就不会了，看了别人的代码才会
在滚第 i 组背包的情况时，可以选择第 i 组选贡献为 0 的背包，其体积可任意选一个，当然是选一个体积把最优的情况转移过来，也就是 下述前缀最大值，看下面代码就知道了
#include<iostream> #include<algorithm> #include<vector> using namespace std; const int INF = 1e9; int a[5002][5002]; int v[5002]; int w[5002]; int dp[5002]; int pre_ma[5002]; bool vis[5002]; struct BB{ int w,v; }; vector<BB>bb[5002]; int main() { int n, k, s, x; cin>>n>>k>>s; for(int i =1;i<=n;i++){ cin>>x; vis[x] = true; a[i%k][x]++; } int tot = 0; for(int i =1;i<=s;i++) ; for(int i = 0;i<k;i++){ for(int j = 0;j<=s;j++){ if(a[i][j]){ bb[i].push_back({j,a[i][j]}); } } } for(int j = 1;j<=s;j++) dp[j] = -INF; for(int i = 0;i<k;i++ ){ for(int j = s;j>=0;j--){ for(int k = 0;k<bb[i].size();k++){ if(j>=bb[i][k].w) dp[j]=max(dp[j],dp[j-bb[i][k].w]+bb[i][k].v); } dp[j] = max(dp[j],pre_ma[j]); } int ma = 0; for(int j = 0;j<= s;j++){ ma = max(ma,dp[j]); pre_ma[j] = ma; } } cout<<n - dp[s]<<endl; return 0; }
选出一个贡献为 0 的背包时，不必担心选的这个数其实是有贡献的 (想一想为什么) ，也不必担心会出现 2 组或多组背包都是 凑出贡献为 0 的背包的情况。
E题：Is-A? Has-A? Who Knowz-A?
给出 n 组 Is-A 和 Has-A关系和m组查询
A is B && B is C -> A is C
A has B && B has C -> A has C
A has B && B is C -> A has C
A is B && B has C -> A has C
A is B 的同时也可以是 A has B
看了别人代码才会，用floyd求传递闭包
has关系是建立在is的基础上，要先把is的关系算好
for(int k = 1;k<=tot;k++){ for(int i = 1;i<=tot;i++){ for(int j = 1;j<=tot;j++){ if(is[i][k]&&is[k][j]) is[i][j] = 1; } } } for(int k = 1;k<=tot;k++){ for(int i = 1;i<=tot;i++){ for(int j = 1;j<=tot;j++){ if(is[i][k]&&has[k][j]) has[i][j] = 1; else if(has[i][k]&&is[k][j]) has[i][j] = 1; else if(has[i][k]&&has[k][j]) has[i][j] = 1; } } }
我试了下，这样写也能过
for(int k = 1;k<=tot;k++){ for(int i = 1;i<=tot;i++){ for(int j = 1;j<=tot;j++){ if(is[i][k]&&is[k][j]) is[i][j] = 1; if(is[i][k]&&has[k][j]) has[i][j] = 1; else if(has[i][k]&&is[k][j]) has[i][j] = 1; else if(has[i][k]&&has[k][j]) has[i][j] = 1; } } }
不怎么清楚这两者的关系......
ac代码：
#include<iostream> #include<algorithm> #include<map> using namespace std; map<string,int> ant; int n,m; int has[503][503]; int is[503][503]; int tot = 0; void add(string s){ if(ant.count(s)) return; tot++; ant[s] = tot; } int main() { cin>>n>>m; string c1,r,c2; for(int i = 1;i<=n;i++){ cin>>c1>>r>>c2; add(c1),add(c2); if(r[0]=='i'){ is[ant[c1]][ant[c2]] = 1; } else{ has[ant[c1]][ant[c2]] = 1; } } for(int i =1;i<=tot;i++) { is[i][i] = 1; } //for(int k = 1;k<=tot;k++){ // for(int i = 1;i<=tot;i++){ // for(int j = 1;j<=tot;j++){ // if(is[i][k]&&is[k][j]) is[i][j] = 1; // } // } //} for(int k = 1;k<=tot;k++){ for(int i = 1;i<=tot;i++){ for(int j = 1;j<=tot;j++){ if(is[i][k]&&is[k][j]) is[i][j] = 1; if(is[i][k]&&has[k][j]) has[i][j] = 1; else if(has[i][k]&&is[k][j]) has[i][j] = 1; else if(has[i][k]&&has[k][j]) has[i][j] = 1; } } } for(int i = 1;i<=m;i++){ cin>>c1>>r>>c2; if(r[0]=='i'){ if(is[ant[c1]][ant[c2]]) cout<< "Query "<<i<<": true"<<endl; else cout<< "Query "<<i<<": false"<<endl; } else{ if(has[ant[c1]][ant[c2]]) cout<< "Query "<<i<<": true"<<endl; else cout<< "Query "<<i<<": false"<<endl; } } return 0; }
F题：Atlantis
想了好久还是不知道怎么做，我太菜了
给 n 个宝藏，得到宝藏分别要 ti 时间，宝藏的高度分别为 hi,水平面每过一个时间上升一米，水没过一个宝藏，这个宝藏就不能拿了，问最多能拿多少个宝藏，1<=n<=200000
先按高度排序，从第一个宝藏开始拿，如果能拿就拿，不能拿就在以前拿过的宝藏里找一个耗时最长的，如果耗时最长的比现在这个宝藏耗时长，且放弃拿耗时最长的宝藏后能拿当前这个宝藏，就把那个耗时最长的宝藏放弃掉，换拿这个宝藏。
#include<iostream> #include<algorithm> #include<queue> using namespace std; struct bz{ long long t,h; }a[200004]; bool cmp(bz a,bz b){ return b.h>a.h; } priority_queue<long long> que; int main() { int n; cin>>n; for(int i =1;i<=n;i++){ cin>>a[i].t>>a[i].h; } sort(a+1,a+n+1,cmp); long long h = 0; int ans = 0; for(int i = 1;i<=n;i++){ if(h+a[i].t<=a[i].h){ h+=a[i].t; que.push(a[i].t); ans++; } else if(!que.empty()){//!que.empty()又忘了。。。 long long tt = que.top(); if(a[i].t<tt&&h-tt+a[i].t<=a[i].h){ que.pop(); que.push(a[i].t); h-=tt; h+=a[i].t; } } } cout<<ans<<endl; }
G H I J 都是签到题