a题是cf 85d原题,
纯数组模拟o(n^2)就过了, zzc的o(n*sqrt(n))的分块都tle了,无力吐槽
int a[100005]; char ss[55]; int main(void) { int n; while (~scanf("%d", &n)){ int l = 0; for (int i=0; i<n; i++) { scanf("%s", ss); if (ss[0] == 's') { long long res = 0; for (int i=2; i<l; i+=5) res += a[i]; printf ("%I64d\n", res); } else { int x; scanf("%d", &x); int t = lower_bound(a, a+l, x) - a; if (ss[0] == 'a') { for (int j=l; j>t; j--) a[j] = a[j-1]; a[t] = x; l++; } else { for (int j=t; j<l; j++) a[j] = a[j+1]; l--; } } } } return 0; }
比赛的时候就水过去2道。
b题 Control 拆点网络流。
int w[N]; void init() { memset (head, -1, sizeof(head)); cnt=0; } int main() { int n, m; while (~scanf("%d%d", &n, &m)) { init(); int t=n*2+2; int si, d; scanf("%d%d", &si, &d); addedge(0, si<<1, inf); addedge(d<<1|1, t, inf); for (int i=1; i<=n; ++i) { scanf("%d", w+i); addedge(i<<1, i<<1|1, w[i]); } for (int i=1; i<=m; ++i) { int a, b; scanf("%d%d", &a, &b); addedge(a<<1|1, b<<1, inf); addedge(b<<1|1, a<<1, inf); } int ans=sap(0, t); printf("%d\n", ans); } }
e题 Food 类似二分图 也要建立额外的原汇店
int main() { int n, f, d; while (~scanf("%d%d%d", &n, &f, &d)) { init(); int sink=f+d+2*n+2; for (int i=0; i<f; ++i) { int x; scanf("%d", &x); add(0, i+1, x); } for (int i=0; i<d; ++i) { int x; scanf("%d", &x); //puts("@@"); add(i+1+f, sink, x); } for (int i=1; i<=n; ++i) { add(f+d+(i<<1), f+d+(i<<1|1), 1); } for (int i=1; i<=n; ++i) { scanf("%s", good); for (int j=0; j<f; ++j) if(good[j]=='Y')add(j+1, f+d+(i<<1), inf); } for (int i=1; i<=n; ++i) { scanf("%s", good); for (int j=0; j<d; ++j) if(good[j]=='Y')add(f+d+(i<<1|1), j+f+1, inf); } int ans=sap(0, sink); printf("%d\n", ans); } }
f题, Groups dp
g题, Multiple dp 和之前浙大月赛的题目很类似。存余数,枚举数字出现的状态
h题, 4 substrings problem dp+枚举状态合并
i题 Buildings 贪心