题解之前
咕咕咕
因为教练不在，玩去了，好几天没有更新。%%%鸽掉的几天这里有（妹子）。
前几天推出了，每天晚上就和几个同学一起准备AC这上面的题，结果奴隶战OTK就花了好久才A。（祭奠天国的战歌）
%%% 辣个男人 又来了。
prob
确实被我一眼秒杀的题，我却被我的傻逼做法秒杀了。
满足条件的一定只需要2道题。（n<=5时）
本来01状态压缩一下不就完事了，但是我脑子一抽，写了如下程序：
#include#include #include #define FN "prob"const int maxn=1e5+5;int a[maxn],d[maxn];int b[maxn],c[maxn];namespace Baoli { void one(int num) { memset(b,0,sizeof(b)); bool fl=false; for(int i=1;i<=num;i++) { char ch;while(!isdigit(ch=getchar())); b[i]=ch-'0'; if(!b[i]) fl=true; } if(fl) printf("YES\n"); else printf("NO\n"); return ; } void two(int num) { memset(b,0,sizeof(b)); memset(c,0,sizeof(c)); int _01=0,_00=0,_10=0; for(int i=1;i<=num;i++) { char ch; while(!isdigit(ch=getchar()));b[i]=ch-'0'; while(!isdigit(ch=getchar()));c[i]=ch-'0'; if(!b[i] && c[i]) _01++; if(!b[i] && !c[i]) _00++; if(b[i] && !c[i]) _10++; } if(_00) printf("YES\n"); else if(_01 && _10) printf("YES\n"); else printf("NO\n"); return ; } void three(int num) { memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(c,0,sizeof(c)); int _000=0,_001=0,_010=0,_011=0,_100=0,_101=0,_110=0; for(int i=1;i<=num;i++) { char ch; while(!isdigit(ch=getchar()));a[i]=ch-'0'; while(!isdigit(ch=getchar()));b[i]=ch-'0'; while(!isdigit(ch=getchar()));c[i]=ch-'0'; if(!a[i] && !b[i] && !c[i]) ++_000; else if(!a[i] && !b[i] && c[i]) ++_001; else if(!a[i] && b[i] && !c[i]) ++_010; else if(!a[i] && b[i] && c[i]) ++_011; else if(a[i] && !b[i] && !c[i]) ++_100; else if(a[i] && !b[i] && c[i]) ++_101; else if(a[i] && b[i] && !c[i]) ++_110; } if(_000 || (_001 && (_010 || _100 || _110)) || (_010 && (_100 || _101)) || (_011 && _100)) printf("YES\n"); else printf("NO\n"); return ; }}int main() { freopen(FN".in","r",stdin); freopen(FN".out","w",stdout); int T;scanf("%d",&T); while(T--) { int n,m;scanf("%d%d",&n,&m); if(m==1) Baoli::one(n); else if(m==2) Baoli::two(n); else if(m==3) Baoli::three(n); else { memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(c,0,sizeof(c)); memset(d,0,sizeof(d)); int _0000=0,_0001=0,_0010=0,_0011=0,_0100=0,_0101=0,_0110=0,_0111=0; int _1000=0,_1001=0,_1010=0,_1011=0,_1100=0,_1101=0,_1110=0; for(int i=1;i<=n;i++) { char ch; while(!isdigit(ch=getchar()));a[i]=ch-'0'; while(!isdigit(ch=getchar()));b[i]=ch-'0'; while(!isdigit(ch=getchar()));c[i]=ch-'0'; while(!isdigit(ch=getchar()));d[i]=ch-'0'; if(!a[i] && !b[i] && !c[i] && !d[i]) ++_0000; else if(!a[i] && !b[i] && !c[i] && d[i]) ++_0001; else if(!a[i] && !b[i] && c[i] && !d[i]) ++_0010; else if(!a[i] && !b[i] && c[i] && d[i]) ++_0011; else if(!a[i] && b[i] && !c[i] && !d[i]) ++_0100; else if(!a[i] && b[i] && !c[i] && d[i]) ++_0101; else if(!a[i] && b[i] && c[i] && !d[i]) ++_0110; else if(!a[i] && b[i] && c[i] && d[i]) ++_0111; else if(a[i] && !b[i] && !c[i] && !d[i]) ++_1000; else if(a[i] && !b[i] && !c[i] && d[i]) ++_1001; else if(a[i] && !b[i] && c[i] && !d[i]) ++_1010; else if(a[i] && !b[i] && c[i] && d[i]) ++_1011; else if(a[i] && b[i] && !c[i] && !d[i]) ++_1100; else if(a[i] && b[i] && !c[i] && d[i]) ++_1101; else if(a[i] && b[i] && c[i] && !d[i]) ++_1110; } if( _0000 || (_0001 && (_0010 || _0100 || _0110 || _1000 || _1010 || _1100 || _1110 ) ) || (_0010 && (_0100 || _0101 || _1000 || _1001 || _1100 || _1101 ) ) || (_0011 && (_0100 || _1000 || _1100 ) ) || (_0100 && (_1000 || _1001 || _1010 || _1011 ) ) || (_0111 && _1000) || (_0101 && (_1000 || _1010) ) || (_0110 && (_1000 || _1001) ) ) printf("YES\n"); else printf("NO\n"); } } return 0;}
清奇的做法，做法惊人的明显，std相当于简化了那些傻逼东西。
我真的不能理解，难道三点钟睡觉对考试状态影响那么大吗？ 但是，这个程序一样完美AC。std::如下
#includeusing namespace std;int n, k;int cnt[1<<4];void yes() { printf("YES\n");}void no() { printf("NO\n");}int main() { freopen("prob.in", "r", stdin); freopen("prob.out", "w", stdout); int T; scanf("%d", &T); while(T--) { scanf("%d%d", &n, &k); memset(cnt, 0, sizeof(cnt)); for(int i = 1; i <= n; i++) { int s = 0; for(int j = 0; j < k; j++) { int v; scanf("%d", &v); if(v) s |= 1<
pizza
贪心。
把一张张饼子看成一个个块，算一个delta，排一下序就知道哪个更适合吃哪一种饼子。 在delta正负分界的地方转换吃的饼子，中间这个块就两种都比较，哪个好吃吃哪个。（其实是披萨）
有这么一个思路，写法千奇百怪。
#includeusing namespace std;const int N = 1e5 + 10;struct Stat { int d, s; Stat(){} Stat(int d, int s):d(d),s(s){}};bool operator<(const Stat &r, const Stat &s) { return r.d > s.d;}int n, S;int s[N], a[N], b[N], d[N];Stat stats[N];long long pres[N];long long cp(long long len) { long long ans = 0; for(int i = 1; i <= n; i++) { if(pres[i] <= len) { ans += (long long)stats[i].s * stats[i].d; } else { ans += (long long)(len - pres[i-1]) * stats[i].d; break; } } return ans;}long long calc(long long s, long long more) { vector vc; for(int i = 1; i <= n; i++) { if(pres[i] >= s) { for(int j = 1; j <= pres[i] - s + 1 && more >= 1; j++) { vc.push_back(stats[i].d); more--; } for(int ii = i + 1; ii <= n && more >= 1; ii++) for(int j = 1; j <= stats[ii].s && more >= 1; j++) { vc.push_back(stats[ii].d); more--; } long long ans = 0; for(int t = 0; t < (int)vc.size(); t++) { if(vc[t] > 0) ans += vc[t]; } return ans; } } return 0;}int main() { freopen("pizza.in", "r", stdin); freopen("pizza.out", "w", stdout); scanf("%d%d", &n, &S); long long sum = 0, ans = 0; for(int i = 1; i <= n; i++) { scanf("%d%d%d", s+i, a+i, b+i); sum += s[i]; ans += (long long)b[i] * s[i]; stats[i] = Stat(a[i] - b[i], s[i]); } sort(stats+1, stats+1+n); for(int i = 1; i <= n; i++) pres[i] = pres[i-1] + stats[i].s; long long m = (sum + S - 1) / S; long long sub = 0; if(stats[n].d >= 0) { for(int i = 1; i <= n; i++) sub += (long long)stats[i].d * stats[i].s; ans += sub; printf("%lld\n", ans); } else { for(int i = 1; i <= n; i++) { if(stats[i].d < 0) { long long subans = ans + cp(pres[i-1] / S * S); long long more = S * m - sum; subans = max(subans, ans + cp(pres[i-1] / S * S + S - more) + calc(pres[i - 1] / S * S + S - more + 1, more)); printf("%lld\n", subans); break; } } }}
scream
我们比较容易想到的一个dp 是用dp[i][j] 前i 个数, 分成j 段, 最大的美味值. 转移为:
dp[i][j] = max dp[k -?1][j - 1] + c(k,j) 然后我们发现dp[i][j] 仅由dp[i][j -? 1] 转移过来, 我们把j 压掉, 然后用数据结构(线段树) 维护右边的max 值#includeusing namespace std;#define prev PREEVEVconst int N = 35000 + 10;const int oo = 0x3f3f3f3f;struct Node;void modify(Node *nd, int lf, int rg, int L, int R, int delta);struct Node { int vmax; int flag; Node *ls, *rs; void update() { vmax = max(ls->vmax, rs->vmax); } void pushdown(int lf, int rg) { if(flag) { int mid = (lf + rg) >> 1; modify(ls,lf,mid,lf,mid,flag); modify(rs,mid+1,rg,mid+1,rg,flag); flag = 0; } }}pool[N*2], *tail, *root;int n, m;int aa[N], pos[N], prev[N];int dp[2][N];int cur = 1, prv = 0;Node *build(int lf, int rg) { Node *nd = ++tail; nd->vmax = nd->flag = 0; if(lf == rg) { nd->vmax = dp[prv][lf]; } else { int mid = (lf + rg) >> 1; nd->ls = build(lf, mid); nd->rs = build(mid+1, rg); nd->update(); } return nd;}void modify(Node *nd, int lf, int rg, int L, int R, int delta) { if(L <= lf && rg <= R) { nd->vmax += delta; nd->flag += delta; return; } int mid = (lf + rg)>>1; nd->pushdown(lf,rg); if( L <= mid ) modify(nd->ls, lf, mid, L, R, delta); if( R > mid ) modify(nd->rs, mid+1, rg, L, R, delta); nd->update();}int query(Node *nd, int lf, int rg, int L, int R) { if(L <= lf && rg <= R) return nd->vmax; int mid = (lf + rg) >> 1; nd->pushdown(lf,rg); int rt = -oo; if( L <= mid ) rt = max( rt, query(nd->ls, lf, mid, L, R) ); if( R > mid ) rt = max( rt, query(nd->rs,mid+1,rg,L,R) ); return rt;}int main() { freopen("scream.in", "r", stdin); freopen("scream.out", "w", stdout); scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) scanf("%d", aa + i); for(int i = 1; i <= n; i++) { prev[i] = pos[aa[i]]; pos[aa[i]] = i; } for(int i = 1; i <= n; i++) dp[prv][i] = dp[prv][i-1] + (prev[i] == 0); for(int k = 2; k <= m; k++) { tail = pool; root = build(1, n); for(int i = 1; i <= n; i++) { if(i < k ) dp[cur][i] = -oo; else { modify(root, 1, n, max(prev[i],1), i - 1, +1); dp[cur][i] = query(root, 1, n, 1, i - 1); } } swap(prv, cur); } printf("%d\n", dp[prv][n]);}
总结（讲垃圾话）
今天T1少写一行掉50分，充分证明晚睡觉的坏处。
T2 90分贪心就很迷。 T3 没时间写。马上开学了，学校人越来越多，PS4完全不敢在党员工作室玩，真的难受。
明天又回家了，开学逼近，作业：1/100。
反正开学就要停课，应该没什么关系吧。妥妥的200+就这么没了。
我的Rank3啊！