题目大意: 一个数 w 从格子 h 走到格子 0 ,每到达一个格子 i 首先w += i。然后有两个格子 d1 和 d2 ,在这两个格子分别w = max(w-u1,0)和w = max(w-u2,0) 。 1≤h≤100,1≤d1,d2≤h,d1=d2 。
按照题意模拟就好了。复杂度 O(h) 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14
#include<bits/stdc++.h> usingnamespacestd;
#define rint register int inlineintrf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;} int w,h,u1,d1,u2,d2; intmain() { w = rf(); h = rf(); u1 = rf(); d1 = rf(); u2 = rf(); d2 = rf(); d2 > d1 ? u1^=u2^=u1^=u2,d1^=d2^=d1^=d2 : 0; for(; h >= d1; w += h--); w = max(w-u1,0); for(; h >= d2; w += h--); w = max(w-u2,0); for(; h; w += h--); printf("%d\n",w); return0; }
当然这是三段等差数列求和,可以 O(1) 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14
#include<bits/stdc++.h> usingnamespacestd;
#define rint register int inlineintrf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;} #define SUM(l,r) ((r-l+1)*(l+r)>>1) int w,h,u1,d1,u2,d2; intmain() { w = rf(); h = rf(); u1 = rf(); d1 = rf(); u2 = rf(); d2 = rf(); d2 > d1 ? u1^=u2^=u1^=u2,d1^=d2^=d1^=d2 : 0; w = max(w+SUM(d1,h)-u1,0); w = max(w+SUM(d2,d1-1)-u2,0); w += SUM(0,d2-1); printf("%d\n",w); return0; }
#define rint register int inlineintrf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;} intmain(){int n = rf(), l = ceil(sqrt(n)); printf("%d\n",(l<<1)-(l*(l-1ll)>=n)); return0;}
题目大意: 给定一个长度为 n 的可能带有小写英文字母、?、*的字符串。每个?可能删除其前面的一个字符,或者什么也不做;每个*可能删除其前面一个字符,或将前面一个字符复制任意若干次,或者什么也不做。操作后删除?和*。求是否能构造一个长度为 k 的字符串并给出一个方案。 n,k≤200 ,保证每个?和*前面一定是小写英文字母。
就是个分类讨论:
如果?和*全部用来删除都不够显然不行;
如果没有*那么只要 k>n 一定不行;
如果 k≤n ,选 n−k 个?或*删掉就行了;
如果 k>n 且有*,那么将某个*前面的字符复制 k−n 次就行了。
O(n+k) 。
1 2 3 4 5 6 7 8 9 10 11 12 13
#include<bits/stdc++.h> usingnamespacestd; #define rint register int inlineintrf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;} string S, T; int n, m, k, a, b; intmain() { cin >> S >> k; n = S.length(); a = count(S.begin(),S.end(),'?'); b = count(S.begin(),S.end(),'*'); m = n-a-b; if(k<m-a-b || (!b&&k>m)) return !printf("Impossible\n"); if(k <= m){for(rint i = 0; i < n; i++) if(m>k&&!isalpha(S[i+1])) i++, m--; elseif(isalpha(S[i])) T += S[i];} else{for(rint i = 0, j = k-m; i < n; i++) if(S[i]=='*') for(; j-->0; T+=T.back()); elseif(isalpha(S[i])) T += S[i];} cout << T << endl; return0; }
#include<bits/stdc++.h> usingnamespacestd; #define rint register int inlineintrf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;} char T[5] = "ACGT"; vector<string> A, O, R; vector<char> v[2]; int n, m, w, ans, t[2]; bool f, ansf; inlinevoidTrans(vector<string> &A){O.resize(m); for(rint i = 0, j; i < m; i++) for(O[i].resize(n), j = 0; j < n; O[i][j] = A[j][i], j++); A = O; O.clear(); n ^= m ^= n ^= m;} inlineintDiff(string &s, vector<char> v){int res = 0; for(rint i = 0; i < m; res += s[i]!=v[i&1], i++); return res;} inlinevoidColor(string &s, vector<char> v){for(rint i = 0; i < m; s[i] = v[i&1], i++);} inlinevoidSolve() { for(rint i = w = 0, j = 0; i < n; i++, j ^= 2) { v[0] = {T[j],T[j|1]}; v[1] = {T[j|1],T[j]}; t[0] = Diff(A[i],v[0]); t[1] = Diff(A[i],v[1]); w += min(t[0],t[1]); Color(O[i],v[t[0]>t[1]]); } if(w < ans) R = O, ansf = f, ans = w; } intmain() { n = rf(); m = rf(); ans = n*m; A.resize(n); for(rint i = 0; i < n; cin >> A[i], i++); O.resize(n); for(rint i = 0; i < n; O[i].resize(m), i++); do{Solve();}while(next_permutation(T,T+4),next_permutation(T,T+4)); Trans(A); f = 1; O.resize(n); for(rint i = 0; i < n; O[i].resize(m), i++); do{Solve();}while(next_permutation(T,T+4),next_permutation(T,T+4)); if(ansf) Trans(R); for(auto &s:R) cout << s << endl; return0; }
题目大意: 给定一棵 n 个点的树,其中 i 号点上有 xi 个价格为 ti 的物品,从 i 的父亲到达 i 的路费是 li 。你从根节点开始向下移动到某个点再返回(你自己决定怎么走),目的是在总花费不超过 T 的前提下买到尽可能多的物品(你自己觉得买哪些)。但在这个过程中,你的敌人会在你到达点 i 之后割断一条 i 到其儿子的边,目的是让你买到的物品尽可能少。求双方最优策略时你的物品数。 2≤n≤105,1≤T≤1018,1≤ti,xi≤106,0≤li≤109 。
我居然会做这道题。只能说明这场Div.2有点简单?
仔细观察不难发现两个过程是独立的,先求出 f[i] 表示到达点 i 再回去时能买到的最多物品(因为路费总长是确定的,物品贪心选就行了)。如果 f[i] 有了不就是个次大值树上递推么。怎么求 f[i] 呢?