给个人认为比较难的题目打上’*’
NOIP2002(clear)
//一个很吼的贪心题，将平均数减掉之后从左往右将影响消除 #include<bits/stdc++.h> using namespace std; ]; int main() { , sum = ; cin >> n; ; i < n ; i++) { cin >> num[i]; sum += num[i]; } sum /= n; ; i < n ; i++) { num[i] -= sum; if(num[i]) { cou++; num[i + ] += num[i]; } } cout << cou; ; }
均分纸牌
//bfs，注意一个串可能可以变换成多个串 #include<bits/stdc++.h> using namespace std; struct p{ string n; int s; }ans; set < string > uni; multimap < string , string > dis; queue < p > q; int main() { string tar , a , b; cin >> ans.n >> tar; q.push(ans); uni.insert(ans.n); while(cin >> a >> b) dis.insert(pair<string , string>(a , b)); while(!q.empty()) { ans = q.front(); q.pop(); ) break; if(ans.n == tar) { cout << ans.s; ; } ans.s++; ; i < ans.n.size() ; i++) ; j <= i ; j++) ))) for(multimap<string , string>::iterator iter = dis.begin() ; iter != dis.end() ; iter++) )) { , j) + iter -> second + , (int)ans.n.length() - i); if(!uni.count(newS)) { uni.insert(newS); p t; t.n = newS; t.s = ans.s; q.push(t); } } } cout << "NO ANSWER!"; ; }
字串变换
//题目叙述似乎不是很清楚，看懂了直接上公式就行 #include<bits/stdc++.h> #define eps 1e-4 //This code is written by Itst using namespace std; int main(){ #ifdef LG freopen("1033.in" , "r" , stdin); //freopen("1033.out" , "w" , stdout); #endif long double H , S , V , L , K , N; cin >> H >> S >> V >> L >> K >> N; long double rangeR = eps + S + L - V * sqrt((H - K) * 0.2) , rangeL = S - eps - V * sqrt(H * 0.2); ; ; i < N ; i++) if(i >= rangeL && i <= rangeR) cnt++; cout << cnt; ; }
自由落体
//爆搜+覆盖剪枝+最优化剪枝 #include<bits/stdc++.h> //This code is written by Itst using namespace std; inline int read(){ ; ; char c = getchar(); while(c != EOF && !isdigit(c)){ if(c == '-') f = ; c = getchar(); } while(c != EOF && isdigit(c)){ a = (a << ) + (a << ) + (c ^ '); c = getchar(); } return f ? -a : a; } ][] , tria[][] , N , K , ans = 0x7fffffff; bool check(int i , int j){ ] < tria[j][] || tria[j][] < tria[i][] || tria[i][] < tria[j][] || tria[i][] > tria[j][]; } void dfs(int now , int sum){ if(sum > ans) return; if(now > N){ ans = sum; return; } ][] , newSum = sum; memcpy(temp , tria , sizeof(tria)); ; i <= K ; i++){ ] < tria[i][]) newSum -= (tria[i][] - tria[i][]) * (tria[i][] - tria[i][]); tria[i][] = min(tria[i][] , node[now][]); tria[i][] = max(tria[i][] , node[now][]); tria[i][] = min(tria[i][] , node[now][]); tria[i][] = max(tria[i][] , node[now][]); newSum += (tria[i][] - tria[i][]) * (tria[i][] - tria[i][]); ; ; f && j <= K ; j++) if(j != i) f = check(i , j); if(f) dfs(now + , newSum); memcpy(tria , temp , sizeof(tria)); newSum = sum; } } int main(){ #ifdef OJ freopen("1034.in" , "r" , stdin); //freopen("1034.out" , "w" , stdout); #endif N = read(); K = read(); ; i <= N ; i++){ node[i][] = read(); node[i][] = read(); } ; i <= K ; i++){ tria[i][] = tria[i][] = ; tria[i][] = tria[i][] = ; } dfs( , ); cout << ans; ; }
*矩形覆盖
NOIP2003(clear)
//拓扑排序模板题 #include<bits/stdc++.h> using namespace std; inline int read(){ ; ; char c = getchar(); while(!isdigit(c)){ ; c = getchar(); } ) + (a << ) + (c ^ ') , c = getchar(); return k ? -a : a; } vector < ] , W[]; ] , U[] , num[]; int main(){ int N = read() , P = read(); queue < int > q; priority_queue < int , vector < int > , greater < int > > q1; ; i <= N ; i++){ if(C[i] = read()){ q.push(i); read(); } else C[i] -= read(); } while(P--){ int a = read() , b = read(); Ed[a].push_back(b); W[a].push_back(read()); num[b]++; } while(!q.empty()){ int t = q.front(); q.pop(); if(Ed[t].size()) ; i ^ Ed[t].size() ; i++){ ) C[Ed[t][i]] += W[t][i] * C[t]; if(!--num[Ed[t][i]]) q.push(Ed[t][i]); } ) q1.push(t); } if(q1.empty()) cout << "NULL"; while(!q1.empty()){ cout << q1.top() << ' ' << C[q1.top()] << endl; q1.pop(); } ; }
神经网络
//区间DP,设f[i][j]表示i到j的点组成的二叉树中得分最高的方式，合并枚举根即可 #include<bits/stdc++.h> using namespace std; ] , p[][]; ][]; void dfs(int f , int l) { if(f >= l) { if(f == l) cout << f << " "; return; } cout << p[f][l] << " "; dfs(f , p[f][l] - ); dfs(p[f][l] + , l); } int main(){ ios::sync_with_stdio(false); cin >> n; ; i <= n ; i++) vis[][i] = ; ; i <= n ; i++) { ; j <= n ; j++) vis[i][j] = ; cin >> num[i]; vis[i][i] = num[i]; } ; i <= n ; i++) vis[n + ][i] = ; ; i <= n - ; i++) ; j + i <= n ; j++) for(int k = j ; k <= j + i ; k++) ] * vis[k + ][j + i] + num[k] > vis[j][i + j]) { vis[j][i + j] = vis[j][k - ] * vis[k + ][j + i] + num[k]; p[j][j + i] = k; } cout << vis[][n] << endl; dfs( , n); ; }
加分二叉树
//暴搜，根据贪心不难知道每一次切断的一定是当前被感染的点和其没被感染的儿子之间的边 #include<bits/stdc++.h> using namespace std; inline int read(){ ; char c = getchar(); while(!isdigit(c)) c = getchar(); ) + (a << ) + (c ^ ) , c = getchar(); return a; } inline int min(int a , int b){ return a < b ? a : b; } vector < ]; queue < int > q; int minN = 0x3f3f3f3f; ]; void choose(int , queue < int >); void create(int num , queue < int > q){ queue < int > q1; register ; while(!q.empty()){ int t = q.front(); q.pop(); num++; ; i < Ed[t].size() ; i++) if(!vis[Ed[t][i]]){ q1.push(Ed[t][i]); if(num + ++sum > minN) return; } } if(num + sum > minN) return; ){ minN = min(minN , num); return; } choose(num , q1); } int main(){ register int n = read() , p = read(); ; i - p ; i++){ int a = read() , b = read(); Ed[a].push_back(b); Ed[b].push_back(a); } q.push(); vis[] = ; create( , q); printf("%d" , minN); ; } void choose(int num , queue < int > q){ register int first = q.front(); do{ vis[q.front()] = ; q.push(q.front()); q.pop(); }while(q.front() - first); do{ register int t = q.front(); q.pop(); create(num , q); q.push(t); }while(q.front() - first); while(!q.empty()){ vis[q.front()] = ; q.pop(); } }
传染病控制
//为什么会有这么玄学的题目？？？ //注意：①I可能为人名；②在某种状态没有人被认为时Guilty的时候，考虑被指正不是Guilty的人；③有可能多种情况同一结果 #include<bits/stdc++.h> //This code is written by Itst using namespace std; inline int read(){ ; ; char c = getchar(); while(c != EOF && !isdigit(c)){ if(c == '-') f = ; c = getchar(); } while(c != EOF && isdigit(c)){ a = (a << ) + (a << ) + (c ^ '); c = getchar(); } return f ? -a : a; } map < string , int > day , name; ][] , notG[][] , date[][] , mark[] , nowG[] , nowNotG[] , nowDate[] , nowNotDate[]; int N , M , P; ]; void check(){ memset(nowG , , sizeof(nowG)); memset(nowNotG , , sizeof(nowNotG)); memset(nowDate , , sizeof(nowDate)); memset(nowNotDate , , sizeof(nowNotDate)); ; i <= M ; i++) if(!mark[i]){ ; j <= M ; j++) if(G[i][j]) nowG[j] = ; ; j <= M ; j++) if(notG[i][j]) nowNotG[j] = ; ; j <= ; j++) if(date[i][j]) nowDate[j] = ; } else{ ; j <= M ; j++) if(G[i][j]) nowNotG[j] = ; ; j <= M ; j++) if(notG[i][j]) nowG[j] = ; ; j <= ; j++) if(date[i][j]) nowNotDate[j] = ; } , ifGuilty = ; ; i <= M ; i++) if(nowG[i]) if(ifGuilty || nowNotG[i]) return; else ifGuilty = ; ; i <= ; i++) if(nowDate[i]) if(ifDate || nowNotDate[i]) return; else ifDate = ; if(!ifGuilty) ; i <= M ; i++) if(!nowNotG[i]) if(!ifGuilty) ifGuilty = ; else{ puts("Cannot Determine"); exit(); } if(ifGuilty){ ; i <= M ; i++) if(nowG[i]){ if(!answer.empty() && answer != ori[i]){ puts("Cannot Determine"); exit(); } answer = ori[i]; return; } ; i <= M ; i++) if(!nowNotG[i]){ if(!answer.empty() && answer != ori[i]){ puts("Cannot Determine"); exit(); } answer = ori[i]; return; } } else{ puts("Cannot Determine"); exit(); } } void dfs(int now , int cnt){ if(now > M){ if(cnt == N) check(); return; } dfs(now + , cnt); mark[now] = ; dfs(now + , cnt + ); mark[now] = ; } int main(){ #ifdef OJ freopen("1039.in" , "r" , stdin); //freopen("1039.out" , "w" , stdout); #endif day[; day[; day[; day[; day[; day[; day[; M = read(); N = read(); P = read(); string s , now; ; i <= M ; i++){ cin >> ori[i]; name[ori[i]] = i; } getline(cin , s); stringstream ss; ; i <= P ; i++){ getline(cin , s); if(!s.empty() && *--s.end() == '\r') s.erase(--s.end()); ss.clear(); ss.str(s); ss >> s; s.erase(--s.end()); int t = name[s]; if(!t) continue; while(ss >> s) if(s == "I"){ ss >> now; if(now != "am"){ if(now != "is" || !name.count("I")) break; int k = name["I"]; ss >> now; if(now != "guilty." && now != "not") break; if(now == "guilty.") G[t][k] = ; else{ ss >> now; if(now == "guilty.") notG[t][k] = ; } continue; } ss >> now; if(now != "guilty." && now != "not") break; if(now == "guilty.") G[t][t] = ; else{ ss >> now; if(now == "guilty.") notG[t][t] = ; } } else if(name.count(s)){ int k = name[s]; ss >> now; if(now != "is") break; ss >> now; if(now != "guilty." && now != "not") break; if(now == "guilty.") G[t][k] = ; else{ ss >> now; if(now == "guilty.") notG[t][k] = ; } } else if(s == "Today"){ ss >> now; if(now != "is") break; ss >> now; if(now.empty()) break; now.erase(--now.end()); if(!day.count(now)) break; date[t][day[now]] = ; } else break; } dfs( , ); if(answer.empty()) puts("Impossible"); else cout << answer; ; }
*侦探推理
NOIP2004(clear)
//... #include<bits/stdc++.h> using namespace std; int main() { , c = ; ; i <= ; i++) { int a; cin >> a; if(mon < a) { cout << "-" << i; ; } c += (mon - a) / * ; mon = (mon - a) % + ; } cout << c / * + mon - ; ; }
津津的储蓄计划
//每一次贪心地合并两个重量最少的果子 #include<bits/stdc++.h> using namespace std; queue <int> p , q; ]; int main(){ ; cin >> n; ; i < n ; i++) cin >> a[i]; sort(a , a + n); ; i < n ; i++) p.push(a[i]); ; !p.empty() || q.size() != ; i++) { int a , b; if(p.empty()) { a = q.front(); q.pop(); } else if(q.empty()) { a = p.front(); p.pop(); } else { int x = p.front() , y = q.front(); if(x <= y) { a = x; p.pop(); } else { a = y; q.pop(); } } if(p.empty()) { b = q.front(); q.pop(); } else if(q.empty()) { b = p.front(); p.pop(); } else { int x = p.front() , y = q.front(); if(x <= y) { b = x; p.pop(); } else { b = y; q.pop(); } } sum += a + b; q.push(a + b); } cout << sum; ; }
合并果子
//DP，从左往右、从右往左做两边LIS算最大权值 #include<bits/stdc++.h> using namespace std; ] , b[] , c[]; int main() { std::ios::sync_with_stdio(false); ; cin >> n; ; i < n ; i++) { cin >> num[i]; ; j + ; j--) if(num[i] > num[j] && b[i] < b[j]) b[i] = b[j]; b[i]++; } ; i + ; i--) { ; j - n ; j++) if(num[i] > num[j] && c[i] < c[j]) c[i] = c[j]; c[i]++; maxN = max(maxN , b[i] + c[i] - ); } cout << n - maxN; ; }
合唱队形
//搜索要注意剪枝（看前边是否有不论进位与否都不满足条件的竖式），也可以高斯消元 #include<bits/stdc++.h> using namespace std; ][]; ] , N , num[] , vis[]; void dfs(int a , int i) { ) { ; i < N ; i++) printf("%d " , num[i]); exit(); } ; k < a ; k++) ][k] - && num[s[][k] - && num[s[][k] - && (num[s[][k] - ][k] - ][k] - ][k] - ][k] - - num[s[][k] - 'A']) % N) return; ][a] - && num[s[][a] - && num[s[][a] - ) { ][a] - ][a] - ][a] - 'A']) { jw[a - ] = (num[s[][a] - ][a] - 'A'] + jw[a]) / N; ]); dfs(a - , ); } } else ) { ][a] - ][a] - 'A'] + jw[a]; ][a] - 'A'] != n % N) return; jw[a - ] = n / N; ][a] - ) { num[s[][a] - 'A'] = n % N; vis[n % N] = ; dfs(a - , ); vis[n % N] = ; num[s[][a] - ; } else dfs(a - , ); } else )) { ; j >= ; j--) if(!vis[j]) { vis[j] = ; num[s[i][a] - 'A'] = j; dfs(a , i + ); num[s[i][a] - ; vis[j] = ; } } else dfs(a , i + ); } int main() { scanf(] , s[] , s[]); memset(num , - , sizeof(num)); dfs(N - , ); ; }
*虫食算
NOIP2005(clear)
//条件判断练习题 #include<bits/stdc++.h> #define I ans[i]. using namespace std; struct scho{ string name; char gb , xb; int numL , aveSco , claSco , scho; inline void input() { cin >> name >> aveSco >> claSco >> gb >> xb >> numL; && numL) scho += ; && claSco > ) scho += ; ) scho += ; ) scho += ; ) scho += ; } }ans[]; int main() { ios::sync_with_stdio(false); , maxScho = - , maxD = ; cin >> n; ; i < n ; i++) { ans[i].input(); sumScho += ans[i].scho; if(maxScho < ans[i].scho) { maxScho = ans[i].scho; maxD = i; } } cout << ans[maxD].name << endl << maxScho << endl << sumScho; ; }
谁拿了最多奖学金
//DP并压缩路径，根据NOIP2017D1T1结论可以知道当路径长度>=72的时候可以直接压成72，因为72以及之后的都一定可以被到达 //然而代码里面压的是2520 #include<bits/stdc++.h> using namespace std; ] , c[] , minN[]; ]; inline int min(int a , int b){ return a < b ? a : b; } int main(){ int L , S , T , M; scanf("%d%d%d%d" , &L , &S , &T , &M); ; i < M ; i++) scanf("%d" , a + i); sort(a , a + M); a[M] = L; c[] = a[] % ; ; i <= M ; i++){ ] , b = tmp % ; && b <= T) b += ; c[i] = c[i - ] + b; } ; i < M ; i++) f[c[i]] = ; memset(minN , 0x3f , sizeof(minN)); minN[] = ; ; i < c[M] ; i++){ for(int j = S; j <= T && j <= i ; j++) minN[i] = min(minN[i] , minN[i - j]); minN[i] += f[i]; } int Min = 0x3f3f3f3f; for(int i = c[M] - T ; i - c[M] ; i++) Min = min(Min , minN[i]); cout << Min; ; }
*过河
//正着、反着把环断成链，考虑最多有多少个人可以不移动 #include<bits/stdc++.h> //This code is written by Itst using namespace std; inline int read(){ ; ; char c = getchar(); while(c != EOF && !isdigit(c)){ if(c == '-') f = ; c = getchar(); } while(c != EOF && isdigit(c)){ a = (a << ) + (a << ) + (c ^ '); c = getchar(); } return f ? -a : a; } ; ]; bool vis[MAXN]; int main(){ #ifdef OJ freopen("1053.in" , "r" , stdin); //freopen("1053.out" , "w" , stdout); #endif , cnt = ; ; i <= N ; i++){ l[i] = read(); r[i] = read(); } pre = l[]; vis[] = ; pot[] = ; ; i <= N ; i++){ if(l[dir] == pre){ pre = dir; dir = r[dir]; } else{ pre = dir; dir = l[dir]; } if(vis[dir]){ puts("-1"); ; } vis[dir] = ; pot[(i - dir + N) % N]++; } ; i < N ; i++) cnt = max(cnt , pot[i]); memset(pot , , sizeof(pot)); pre = r[]; dir = ; pot[] = ; ; i <= N ; i++){ if(l[dir] == pre){ pre = dir; dir = r[dir]; } else{ pre = dir; dir = l[dir]; } pot[(i - dir + N) % N]++; } ; i < N ; i++) cnt = max(cnt , pot[i]); printf("%d\n" , N - cnt); ; }
篝火晚会
//找到值带入a即可 #include<bits/stdc++.h> #define int long long //This code is written by Itst using namespace std; inline int read(){ ; ; char c = getchar(); while(c != EOF && !isdigit(c)){ if(c == '-') f = ; c = getchar(); } while(c != EOF && isdigit(c)){ a = (a << ) + (a << ) + (c ^ '); c = getchar(); } return f ? -a : a; } ; ][] = { , , , , , , , , , , , }; ] = "()^*+-"; ]; ]; ] , pos[]; map < char , int > ctoi; int calc(int a , int b , int pos){ ; switch(pos){ : while(b){ ) ans = ans * a % MOD; a = a * a % MOD; b >>= ; } break; : ans = a * b % MOD; break; : ans = (a + b) % MOD; break; : ans = (a - b + MOD) % MOD; break; } return ans; } int calc(string s , int a){ , topPos = , nowNum = ; ; pos[] = ; s = s + ")"; ; i < s.size() ; i++) if(s[i] == ' ' || s[i] == '\r' || s[i] == '\n') continue; else if(isdigit(s[i])){ nowNum = nowNum * + s[i] - '; f = ; } else if(s[i] == 'a') num[++topNum] = a; else{ if(f){ num[++topNum] = nowNum; nowNum = f = ; } int t = ctoi[s[i]]; ] > yxj[t][]){ num[topNum - ] = calc(num[topNum - ] , num[topNum] , pos[topPos]); topNum--; topPos--; } ] == yxj[t][]) topPos--; else pos[++topPos] = t; } ]; } inline void getString(string& s){ char c = getchar(); while(c == '\r' || c == '\n') c = getchar(); while(!(c == '\r' || c == '\n' || c == EOF)){ s = s + c; c = getchar(); } } signed main(){ #ifdef OJ freopen("1054.in" , "r" , stdin); //freopen("1054.out" , "w" , stdout); #endif ; i < ; i++) ctoi[to[i]] = i; getString(mod); int N = read(); ; i <= N ; i++) getString(now[i]); ; i <= ; i++){ int t = calc(mod , i); ; j <= N ; j++) if(calc(now[j] , i) != t) vis[j] = ; } ; i <= N ; i++) if(!vis[i]) putchar(i + ); ; }
等价表达式
NOIP2006(clear)
//区间DP、断环成链 #include<bits/stdc++.h> #define ll long long using namespace std; inline ll fast_read() { char c = getchar(); ll a = ; ; while(!isdigit(c)) { ; c = getchar(); } ) + (a << ) + c - ' , c = getchar(); return k ? -a : a; } inline void fast_print(ll x) { ] , dirN = -; ) putchar('-') , x = -x; , x /= ; ) putchar('); ) putchar(num[dirN--] + ); putchar('\n'); } ] , maxN[][]; int main() { ; ; i < m ; i++) num[i] = fast_read(); ; i <= m ; i++) ; j < m ; j++) ; k < i + j ; k++) maxN[j][(i + j) % m] = max(maxN[j][(i + j) % m] , maxN[j][k % m] + maxN[k % m][(i + j) % m] + num[j] * num[k % m] * num[(j + i) % m]); ; i < m ; i++) maxAll = max(maxAll , maxN[i][i]); fast_print(maxAll); ; }
能量项链
//依赖背包弱化版，直接枚举一棵依赖关系树里面的选择即可 #include<bits/stdc++.h> using namespace std; struct ys{ ] , wei[] , index; }ans[]; ] , visa[]; int main() { ; cin >> N >> M; N /= ; ; i <= M ; i++) { int a , b , c; cin >> a >> b >> c; a /= ; if(c) { ; i < dirA ; i++) if(ans[i].index == c) { ) { ans[i].wei[] = ans[i].wei[] + a; ans[i].mon[] = ans[i].mon[] + a * b; } else { ans[i].wei[] = ans[i].wei[] + a; ans[i].wei[] = ans[i].wei[] + a; ans[i].mon[] = ans[i].mon[] + a * b; ans[i].mon[] = ans[i].mon[] + a * b; } ans[i].dirN++; } } else{ ans[dirA].dirN = ; ans[dirA].mon[] = a * b; ans[dirA].wei[] = a; ans[dirA++].index = i; } } ; i < dirA ; i++) { ; j <= N ; j++) visa[j] = vis[j]; ; j < && ans[i].mon[j] ; j++) ; k--) visa[k + ans[i].wei[j]] = max(visa[k + ans[i].wei[j]] , vis[k] + ans[i].mon[j]); ; j <= N ; j++) vis[j] = visa[j]; } cout << vis[N] * ; ; }
金明的预算方案
//递推，设f[i][j]表示从后往前第i位，数字为j时候的方案数，记得写高精 #include<bits/stdc++.h> using namespace std; struct BigNum{ ]; BigNum(){ memset(num , , sizeof(num)); } void operator =(int k){ while(k){ num[++num[]] = k % ; k /= ; } } BigNum operator +(BigNum a){ BigNum c; c.num[] = num[] > a.num[] ? num[] : a.num[]; ; i <= c.num[] ; i++) ){ ++c.num[i + ]; c.num[i] -= ; } ] + ]) ++c.num[]; return c; } inline void output(){ ]) putchar('); ] ; i ; i--) putchar(num[i] + ); } }; , , , , , , , , , }; BigNum sum , *ans[]; int main() { int K , W; cin >> K >> W; ; i <= W / K + ; i++) ans[i] = new BigNum[pow2[K]]; ; i < pow2[K] ; i++) ans[][i] = ; ; (j - ) * K < W ; j++) ; k ; k--){ ans[j][k] = ans[j][k + ] + ans[j - ][k + ]; ) * K < W) sum = sum + ans[j][k]; } sum.output(); ; }
2^k进制数
//模拟题 #include<bits/stdc++.h> //This code is written by Itst using namespace std; inline int read(){ ; ; char c = getchar(); while(c != EOF && !isdigit(c)){ if(c == '-') f = ; c = getchar(); } while(c != EOF && isdigit(c)){ a = (a << ) + (a << ) + (c ^ '); c = getchar(); } return f ? -a : a; } ] , to[][] , times[][] , need[] , spend[]; ][]; int main(){ #ifdef OJ freopen("1065.in" , "r" , stdin); //freopen("1065.out" , "w" , stdout); #endif M = read(); N = read(); ; ; i <= N * M ; i++) need[i] = read(); ; i <= N ; i++) ; j <= M ; j++) to[i][j] = read(); ; i <= N ; i++) ; j <= M ; j++) times[i][j] = read(); ; i <= N * M ; i++){ in[need[i]]++; ; j++){ ; ; f && k < times[need[i]][in[need[i]]] ; k++) if(vis[to[need[i]][in[need[i]]]][j + k]){ f = ; j = j + k; } if(f){ ; k < times[need[i]][in[need[i]]] ; k++) vis[to[need[i]][; maxN = max(maxN , j + times[need[i]][in[need[i]]]); spend[need[i]] = j + times[need[i]][in[need[i]]]; break; } } } cout << maxN; ; }
作业调度方案
NOIP2007(clear)
//又要写高精...每一行是独立的，考虑区间DP，（倒序DP方式：）设f[i][j]表示最后选择i到j的最大得分，每一次枚举左右即可。 #include<bits/stdc++.h> using namespace std; struct BN{ ]; int& operator [](int x){return num[x];} BN& operator =(const char *c){ , k = ; ; i <= n ; i++){ ) j++ , k = ; num[j] += k * (c[n - i] ^ ); k = (k << ) + (k << ); } num[] = j; return *this; } BN(){memset(num , , sizeof(num));} BN(const BN &a){memcpy(num , a.num , sizeof(num));} BN( , sizeof(num));*this = s;} BN operator +(BN a){ BN c; c[] = max(a[] , num[]); ; i <= c[] ; i++) ){ c[i + ]++; c[i] -= ; } ] + ]) ++c[]; return c; } BN operator *(int a){ BN c; c[] = num[]; ; i <= num[] ; i++) c[i] = num[i] << ; ; i <= c[] ; i++) ){ c[i + ] += c[i] / ; c[i] %= ; } ] + ]) c[]++; return c; } }maxN[][]; inline BN input(){ ] = {}; scanf("%s" , c); return BN(c); } inline void output(BN n){ printf(]]); ]) printf(]]); } inline BN max(BN a , BN b){ ] > b[]) return a; ] < b[]) return b; ] ; i ; i--) if(a[i] > b[i]) return a; else if(a[i] < b[i]) return b; return a; } int main(){ BN sum; int N , M; for(scanf("%d%d" , &N , &M) ; N ; N--){ ; i <= M ; i++) maxN[i][i] = input(); ; i ^ M ; i++) ; j + i <= M ; j++) maxN[j][j + i] = max(maxN[j][j] + maxN[j + ][j + i] * , maxN[j + i][j + i] + maxN[j][j + i - ] * ); sum = sum + maxN[][M] * ; } output(sum); ; }
矩阵取数游戏
//随你怎么写，不用桶排序就行 #include<bits/stdc++.h> #define ll long long using namespace std; inline ll fast_read() { char c = getchar(); ll a = ; ; while(!isdigit(c)) { ; c = getchar(); } ) + (a << ) + c - ' , c = getchar(); return k ? -a : a; } inline void fast_print(ll x) { ] , dirN = -; ) putchar('-') , x = -x; , x /= ; ) putchar('); ) putchar(num[dirN--] + ); } map < int , int > m; int main() { for(int n = fast_read() ; n ; n--) m[fast_read()]++; for(map < int , int >::iterator i = m.begin() ; i != m.end() ; i++) { fast_print(i -> first); putchar(' '); fast_print(i -> second); putchar('\n'); } ; }
统计数字
//模拟题，务必注意细节 #include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); int p1 , p2 , p3; string s; cin >> p1 >> p2 >> p3 >> s; ; i < s.size() ; i++) if(s[i] - '-') cout << s[i]; else{ ] >= s[i + ] || !((s[i - ] >= ] >= ] >= ] >= ] <= ] <= '))) cout << s[i]; else { string st; ] + ; k < s[i + ] ; k++) ; j < p2 ; j++) st += k; ) reverse(st.begin() , st.end()); switch(p1) { : cout << st; break; : { ; i < st.size() ; i++) if(st[i] >= 'a') st[i] -= 'a' - 'A'; cout << st; break; } default: cout << string(st.size() , '*'); } } } ; }
字符串的展开
//进阶指南上面讲得很好啊qwq要在这里说要说很多所以就自行领悟吧qwq话说这道题的直径有很好的性质 #include<bits/stdc++.h> #define LG //This code is written by Itst using namespace std; inline int read(){ ; ; char c = getchar(); while(c != EOF && !isdigit(c)){ if(c == '-') f = ; c = getchar(); } while(c != EOF && isdigit(c)){ a = (a << ) + (a << ) + (c ^ '); c = getchar(); } return f ? -a : a; } ; struct Edge{ int end , upEd , w; }Ed[MAXN << ]; ] , head[MAXN] , N , cntEd = , maxLen , maxDir , cntRoute , sum; inline void addEd(int a , int b , int c){ Ed[++cntEd].end = b; Ed[cntEd].upEd = head[a]; Ed[cntEd].w = c; head[a] = cntEd; } void dfs(int now , int fa , int len){ for(int i = head[now] ; i ; i = Ed[i].upEd) if(Ed[i].end != fa){ pre[Ed[i].end] = i; dfs(Ed[i].end , now , len + Ed[i].w); } if(maxLen < len){ maxLen = len; maxDir = now; } } void getRoute(int start , int end){ while(end != start){ route[++cntRoute][] = end; route[cntRoute][] = Ed[pre[end]].w; sum += Ed[pre[end]].w; end = Ed[pre[end] ^ ].end; } route[++cntRoute][] = start; } void Dfs(int now , int belong , int fa , int len){ for(int i = head[now] ; i ; i = Ed[i].upEd) ][] && Ed[i].end != route[belong + ][]) Dfs(Ed[i].end , belong , now , len + Ed[i].w); maxL[belong] = max(maxL[belong] , len); } int main(){ #ifdef LG freopen("1099.in" , "r" , stdin); //freopen("1099.out" , "w" , stdout); #endif N = read(); int S = read(); ; i < N ; i++){ int a = read() , b = read() , c = read(); addEd(a , b , c); addEd(b , a , c); } dfs( , , ); int t = maxDir; maxLen = ; dfs(t , , ); getRoute(t , maxDir); , q = , lenP = , dis = , lenQ = sum , maxAll = , ans = 0x7fffffff; ; i <= cntRoute ; i++){ Dfs(route[i][] , i , , ); maxAll = max(maxAll , maxL[i]); } do{ ] <= S){ lenQ -= route[q][]; dis += route[q++][]; } ans = min(ans , max(maxAll , max(lenP , lenQ))); lenP += route[p][]; dis -= route[p++][]; }while(q < cntRoute); cout << ans; ; }
*树网的核
NOIP2008(clear)
//DP，设f[i][j][k]表示第一条路径走到(j,i-j)，第二条路径走到(k,i-k)时的最大和，每一次枚举向右还是向下，注意路径不能相交//当然写费用流也是可以的（逃#include<bits/stdc++.h>#define ll long longusing namespace std;inline ll fast_read(){ char c = getchar(); ll a = ; ; while(!isdigit(c)) { ; c = getchar(); } ) + (a << ) + c - ' , c = getchar(); return k ? -a : a;}inline void fast_print(ll x){ ] , dirN = -; ) putchar('-') , x = -x; , x /= ; ) putchar('); ) putchar(num[dirN--] + ); putchar('\n');}][] , ans[][][];int main(){ int M = fast_read() , N = fast_read(); ; i <= M ; i++) ; j <= N ; j++) num[i][j] = fast_read(); ; i <= N + M ; i++) , i - M) ; k <= min(N , i - ) ; k++) ) ; l++) { ans[i][k][l] = max(ans[i - ][k][l] , max(ans[i - ][k][l - ] , max(ans[i - ][k - ][l - ] , ans[i - ][k - ][l]))) + (k - l ? num[i - k][k] + num[i - l][l] : num[i - k][k]); } fast_print(ans[N + M][N][N]); ;}
传纸条
//按题意模拟 #include<bits/stdc++.h> using namespace std; ]; bool ifZ(int a) { ) return false; ; i * i <= a ; i++) ) return false; return true; } int main() { ios::sync_with_stdio(false); string s; , minN = ; cin >> s; ; i < s.size() ; i++) maxN = max(maxN , ++num[s[i] - 'a']); ; i < ; i++) if(num[i] && num[i] < minN) minN = num[i]; if(ifZ(maxN - minN)) cout << "Lucky Word" << endl << maxN - minN; ; ; }
笨小猴
//爆搜、打表都可以 #include<bits/stdc++.h> using namespace std; inline int hcb(int a) { ; ) { ) { : : : sum += ;break; : sum += ;break; : sum += ;break; : sum += ;break; : sum += ;break; ; } a /= ; } switch(a) { : : : sum += ;break; : sum += ;break; : sum += ;break; : sum += ;break; : sum += ;break; ; } return sum; } int main() { ios::sync_with_stdio(false); ; cin >> n; n -= ; ; i <= ; i++) ; j++) if(hcb(i) + hcb(j) + hcb(i + j) == n) ; else cou++; cout << cou; ; }
火柴棒等式
//贪心地对第一个栈进行操作，如果后面有只能加入第一个栈的数字才考虑将当前数字加入第二个栈 #include<bits/stdc++.h> #define LG //This code is written by Itst using namespace std; inline int read(){ ; ; char c = getchar(); while(c != EOF && !isdigit(c)){ if(c == '-') f = ; c = getchar(); } while(c != EOF && isdigit(c)){ a = (a << ) + (a << ) + (c ^ '); c = getchar(); } return f ? -a : a; } ] , s2[] , num[] , top1 , top2 , cntStep , now; ]; ]; int main(){ #ifdef LG freopen("1155.in" , "r" , stdin); //freopen("1155.out" , "w" , stdout); #endif int N = read(); s1[] = s2[] = ; ; i <= N ; i++) num[i] = read(); ; i <= N ; i++){ ; memset(vis , , sizeof(vis)); ; j <= N ; j++) if(num[j] > s2[top2]){ ; f && k < num[i] ; k++) if(!vis[k]) f = ; break; } else vis[num[j]] = ; if(f && s1[top1] > num[i]){ s1[++top1] = num[i]; step[++cntStep] = 'a'; ){ ++now; --top1; step[++cntStep] = 'b'; } } else{ ){ ++now; --top2; step[++cntStep] = 'd'; } if(s2[top2] < num[i]){ puts("); ; } s2[++top2] = num[i]; step[++cntStep] = 'c'; } } while(top1 || top2) ){ ++now; --top1; step[++cntStep] = 'b'; } else{ ++now; --top2; step[++cntStep] = 'd'; } ; i <= cntStep ; i++){ putchar(step[i]); putchar(' '); } ; }
*双栈排序
NOIP2009(clear)
//细节多得不行！！！ #include<bits/stdc++.h> using namespace std; ] , dy[]; int main(){ ios::sync_with_stdio(false); string s1 , s2 , s3; cin >> s1 >> s2 >> s3; ; i < s1.size() ; i++) { || dy[s2[i] - ) { cout << "Failed"; ; } mw[s1[i] - ; dy[s2[i] - ; } ; i < ; i++) if(!mw[i] || !dy[i]) { cout << "Failed"; ; } ; i < s3.size() ; i++) cout << (); ; }
潜伏者
//枚举质数，对于每个质数分类讨论考虑取值个数 #include<bits/stdc++.h> using namespace std; ]; ] , cnt; inline int getNum(long long &a , int i){ ; ){ a /= i; cnt++; } return cnt; } inline int min(int a , int b){return a < b ? a : b;} inline int max(int a , int b){return a > b ? a : b;} int main(){ ; i <= ; i++) if(!prime[i]){ num[cnt++] = i; ; j++) prime[i * j] = ; } long long l1 , r1 , l2 , r2 , N , a0 , a1 , b0 , b1; for(scanf("%lld" , &N) ; N ; N--){ ; scanf("%lld%lld%lld%lld" , &a0 , &a1 , &b0 , &b1); ; i < cnt && a0 + a1 + b0 + b1 - && sum ; i++){ int f1 = getNum(a0 , num[i]) , f2 = getNum(a1 , num[i]); ; else if(f1 > f2) l1 = r1 = f2; ; f1 = getNum(b0 , num[i]); f2 = getNum(b1 , num[i]); , r2 = f1; ; else l2 = r2 = f2; l1 = max(l1 , l2); r1 = min(r1 , r2); ) sum = ; sum *= (r1 - l1 + ); } ){ int f1 = getNum(b0 , a0), f2 = getNum(b1 , a0); , r2 = f1; ; else l2 = r2 = f2; f2 = getNum(a1 , a0) , f1 = getNum(a0 , a0); ; else if(f1 > f2) l1 = r1 = f2; ; l1 = max(l1 , l2); r1 = min(r1 , r2); sum *= (r1 - l1 + ); } ){ int f1 = getNum(b0 , a1), f2 = getNum(b1 , a1); , r2 = f1; ; else l2 = r2 = f2; f1 = getNum(a0 , a1) , f2 = getNum(a1 , a1); ; else if(f1 > f2) l1 = r1 = f2; ; l1 = max(l1 , l2); r1 = min(r1 , r2); sum *= (r1 - l1 + ); } ){ int f1 = getNum(a0 , b0) , f2 = getNum(a1 , b0); ; else if(f1 > f2) l1 = r1 = f2; ; f2 = getNum(b1 , b0); f1 = getNum(b0 , b0); , r2 = f1; ; else l2 = r2 = f2; l1 = max(l1 , l2); r1 = min(r1 , r2); sum *= (r1 - l1 + ); } ){ int f1 = getNum(a0 , b1) , f2 = getNum(a1 , b1); ; else if(f1 > f2) l1 = r1 = f2; ; f1 = getNum(b0 , b1); f2 = getNum(b1 , b1); , r2 = f1; ; else l2 = r2 = f2; l1 = max(l1 , l2); r1 = min(r1 , r2); sum *= (r1 - l1 + ); } printf("%lld\n" , sum); } ; }
*Hankson的趣味题
//缩点+记忆化搜索 #include<bits/stdc++.h> #define MAXN 100001 using namespace std; inline int read(){ ; char c = getchar(); while(!isdigit(c)) c = getchar(); ) + a + (c ^ ') , c = getchar(); return a; } inline int min(int a , int b){return a < b ? a : b;} inline int max(int a , int b){return a > b ? a : b;} vector < int > Ed[MAXN] , Ed_SCC[MAXN]; int Stack[MAXN] , inSCC[MAXN] , dfn[MAXN] , low[MAXN] , MAX[MAXN] , MIN[MAXN] , pri[MAXN]; int ts , N , M , head , num , ans; bool vis[MAXN] , in[MAXN] , visSCC[MAXN]; void findSCC(int a){ Stack[++head] = a; vis[a] = ; dfn[a] = low[a] = ++ts; ; i < Ed[a].size() ; i++){ if(!vis[Ed[a][i]]) findSCC(Ed[a][i]); else if(!in[Ed[a][i]]) continue; low[a] = min(low[a] , low[Ed[a][i]]); } if(dfn[a] == low[a]){ num++; do{ ; inSCC[Stack[head]] = num; Ed_SCC[num].push_back(Stack[head]); MAX[num] = max(MAX[num] , pri[Stack[head]]); MIN[num] = min(MIN[num] , pri[Stack[head]]); }while(Stack[head--] != a); } } bool dfs(int a , int lowBuy){ if(in[a]) return visSCC[a]; ; ; lowBuy = min(lowBuy , MIN[a]); ; i < Ed_SCC[a].size() ; i++) ; j < Ed[Ed_SCC[a][i]].size() ; j++) if(inSCC[Ed[Ed_SCC[a][i]][j]] != a) if(dfs(inSCC[Ed[Ed_SCC[a][i]][j]] , lowBuy)){ visSCC[a] = ; MAX[a] = max(MAX[a] , MAX[inSCC[Ed[Ed_SCC[a][i]][j]]]); } if(visSCC[a]){ ans = max(ans , MAX[a] - lowBuy); ; } ; } int main(){ N = read(); M = read(); ; i <= N ; i++) pri[i] = read(); while(M--){ int a = read() , b = read() , c = read(); Ed[a].push_back(b); ) Ed[b].push_back(a); } memset(MIN , 0x3f , sizeof(MIN)); ; i <= N ; i++) if(!vis[i]) findSCC(i); dfs(inSCC[] , 0x3f3f3f3f); cout << ans; ; }
*最优贸易
//需要比较强的剪枝 #include<bits/stdc++.h> #define K num[i][j].num using namespace std; ; struct kuai{ ] , qz; void init() { fs = ; memset(vis , , ); } }; kuai num[][]; inline void add(int i , int j); inline void erase(int i , int j); void dfs(int i , int j); void find(); int main(){ ; i < ; i++) ; j < ; j++) { num[i][j].init(); num[i][j].qz = - max(abs(i - ) , abs(j - )); } ; i < ; i++) ; j < ; j++) { scanf("%d" , &K); if(K) add(i , j); } find(); cout << maxN; ; } inline void add(int i , int j) { ; k < ; k++) { if(!num[i][k].vis[K]) num[i][k].fs--; num[i][k].vis[K]++; if(!num[k][j].vis[K]) num[k][j].fs--; num[k][j].vis[K]++; } * ; m < i / * + ; m++) * ; n < j / * + ; n++) { if(!num[m][n].vis[K]) num[m][n].fs--; num[m][n].vis[K]++; } } inline void erase(int i , int j) { ; k < ; k++) { ) num[i][k].fs++; num[i][k].vis[K]--; ) num[k][j].fs++; num[k][j].vis[K]--; } * ; m < i / * + ; m++) * ; n < j / * + ; n++) { ) num[m][n].fs++; num[m][n].vis[K]--; } } void dfs(int i , int j) { ; k <= ; k++) if(!num[i][j].vis[k]) { K = k; add(i , j); find(); erase(i , j); K = ; } } void find() { , minX = , minY = ; ; i >= && min - ; i--) ; j >= && min - ; j--) if(!K && !num[i][j].fs) return; else if(min > num[i][j].fs && num[i][j].fs && !K) { min = num[i][j].fs; minX = i; minY = j; } ) { ; ; i < ; i++) ; j < ; j++) numm += K * num[i][j].qz; maxN = max(maxN , numm); } else dfs(minX , minY); }
*靶形数独
NOIP2010(clear)
//送分题 #include<bits/stdc++.h> using namespace std; ]; int main() { , n , m; for(cin >> m >> n ; n ; n--) { ; cin >> k; ; f && i < min(dirNum , m) ; i++) ; if(f) num[dirNum++ % m] = k; } cout << dirNum; ; }
机器翻译
//并查集or二分图 #include<bits/stdc++.h> using namespace std; inline int read(){ ; char c = getchar(); while(!isdigit(c)) c = getchar(); ) + (a << ) + (c ^ ') , c = getchar(); return a; } struct ani{ ][]; int* operator [](int a){return father[a];} //0same，1dif }ans[]; pair < int , int > find(int a , int b){ ]][b][] ^ ans[a][b][]){ pair < ] , ans[a][b][]); ans[a][b][] = t.first; ans[a][b][] = t.second; } ] , ans[a][b][]); } struct Ed{ int a , b , wei; }now[]; bool cmp(Ed a , Ed b){ return a.wei > b.wei; } int main(){ int N = read() , M = read(); ; i <= N ; i++) ; j ^ ; j++){ ans[i][j][] = i; ans[i][j][] = j; } ; i ^ M ; i++){ now[i].a = read(); now[i].b = read(); now[i].wei = read(); } sort(now , now + M , cmp); ; i < M ; i++){ ) == find(now[i].b , )){ cout << now[i].wei; ; } ; j ^ ; j++){ pair < int , int > t1 = find(now[i].a , j) , t2 = find(now[i].b , !j); ans[t1.first][t1.second][] = t2.first; ans[t1.first][t1.second][] = t2.second; //cout << t1.first << " " << t1.second << endl << t2.first << " " << t2.second << endl; } } cout << ; ; }
关押罪犯
//设f[i][j][k][l]为使用了i个1、j个2、k个3、l个4时的最大得分，随便转移，或者记忆化 #include<bits/stdc++.h> #define ll long long using namespace std; inline ll fast_read() { char c = getchar(); ll a = ; ; while(!isdigit(c)) { ; c = getchar(); } ) + (a << ) + c - ' , c = getchar(); return k ? -a : a; } inline void fast_print(ll x) { ] , dirN = -; ) putchar('-') , x = -x; , x /= ; ) putchar('); ) putchar(num[dirN--] + ); putchar('\n'); } ] , kp[][][][] , pot[]; int main() { ll N = fast_read() , M = fast_read(); ; i < N ; i++) score[i] = fast_read(); ; i < M ; i++) { int q = fast_read(); pot[q]++; } ; i <= pot[] ; i++) ; j <= pot[] ; j++) ; p <= pot[] ; p++) ; q <= pot[] ; q++) { : , j1 = j ? j - : , p1 = p ? p - : , q1 = q ? q - : ; kp[i][j][p][q] = max(kp[i1][j][p][q] , max(kp[i][j1][p][q] , max(kp[i][j][p1][q] , kp[i][j][p][q1]))) + score[i + j * + p * + q * ]; } fast_print(kp[pot[]][pot[]][pot[]][pot[]]); ; }
乌龟棋
NOIP2011(clear)
//不要开10w*10w数组啊喂 #include<bits/stdc++.h> using namespace std; ][]; int main() { std::ios::sync_with_stdio(false); int n , a , b; cin >> n; ; i < n ; i++) cin >> c[i][] >> c[i][] >> c[i][] >> c[i][]; cin >> a >> b; ; i + ; i--) ] && a <= c[i][] + c[i][] && b >= c[i][] && b <= c[i][] + c[i][]) { cout << i + ; ; } cout << -; ; }
铺地毯
//将还没有一个在它后面的价格小于p的客栈的数量和已经有的客栈的数量统计下来，每一次来一个客栈更新一次并贡献答案 #include<bits/stdc++.h> using namespace std; inline long long read(){ ; char c = getchar(); while(!isdigit(c)) c = getchar(); ) + (a << ) + (c ^ ') , c = getchar(); return a; } ][]; int main(){ ; while(n--){ int a = read() , b = read(); if(b <= p) ; i ^ k ; i++){ num[i][] += num[i][]; num[i][] = ; } sum += num[a][]; ]++; ]++; } cout << sum; ; }
选择客栈
//搜索，（因为似乎数据保证刚好$N$步完成）所以相同色块一定不动；如果存在色块数量为1or2就剪枝；因为左移优先级低，所以通过左移交换两个块一定不优 #include<bits/stdc++.h> //This code is written by Itst using namespace std; inline int read(){ ; ; char c = getchar(); while(c != EOF && !isdigit(c)){ if(c == '-') f = ; c = getchar(); } while(c != EOF && isdigit(c)){ a = (a << ) + (a << ) + (c ^ '); c = getchar(); } return f ? -a : a; } ][] = {,,,-,,,-,}; ][] , N , now[][] , num[]; ][]; void output(){ ; i < N ; i++) printf(] , now[i][] , now[i][]); exit(); } inline void drop(){ ; i < ; i++) ; j < ; j++) if(col[i][j]){ ; && !col[i][p]){ col[i][p] = col[i][p + ]; col[i][p + ] = ; p--; } } } inline bool search(){ ; memset(vis , , sizeof(vis)); ; i < ; i++) ; j < && col[i][j] ; j++) ] && col[i][j] == col[i][j + ]) vis[i][j] = vis[i][j + ] = vis[i][j + ] = ; ; i < ; i++) ; j < ; j++) ][j] && col[i][j] == col[i + ][j]) vis[i][j] = vis[i + ][j] = vis[i + ][j] = ; ; i < ; i++) ; j < ; j++) if(vis[i][j]){ num[col[i][j]]--; f = ; col[i][j] = ; } return f; } inline void maintain(){ do{ drop(); }while(search()); } void dfs(int step){ ; ; i <= ; i++) || num[i] == ) return; else if(num[i]) cnt = ; if(!cnt){ output(); return; } if(step == N) return; ][] , tnum[]; memcpy(t , col , sizeof(col)); memcpy(tnum , num , sizeof(num)); ; i < ; i++) ; j < ; j++) ; k >= - ; k -= ) && i + k < && col[i][j] && col[i][j] != col[i + k][j] && (k == || !col[i + k][j])){ swap(col[i][j] , col[i + k][j]); now[step][] = i; now[step][] = j; now[step][] = k; maintain(); dfs(step + ); memcpy(col , t , sizeof(col)); memcpy(num , tnum , sizeof(tnum)); } } int main(){ #ifdef LG freopen("1312.in" , "r" , stdin); //freopen("1312.out" , "w" , stdout); #endif N = read(); ; i < ; i++) ; j < ; j++) if(!(col[i][j] = read())) break; else ++num[col[i][j]]; dfs(); puts("-1"); ; }
*Mayan游戏
//二项式定理 #include<bits/stdc++.h> #define ll long long using namespace std; inline ll fast_read() { char c = getchar(); ll a = ; ; while(!isdigit(c)) { ; c = getchar(); } ) + (a << ) + c - ' , c = getchar(); return k ? -a : a; } inline void fast_print(ll x) { ] , dirN = -; ) putchar('-') , x = -x; , x /= ; ) putchar('); ) putchar(num[dirN--] + ); } ll square[][] = {{}}; int main() { ll a = fast_read() , b = fast_read() , k = fast_read() , n = fast_read() , m = fast_read() , num = ; ; i <= k ; i++) { square[i][] = ; ; j <= i ; j++) square[i][j] = (square[i - ][j] + square[i - ][j - ]) % ; } ; i < n ; i++) num = num * a % ; ; i < m ; i++) num = num * b % ; fast_print(num * square[k][n] % ); ; }
计算系数
//二分+前缀和 #include<bits/stdc++.h> #define MAXN 200001 #define ll long long using namespace std; inline ll read(){ ll a = ; char c = getchar(); while(!isdigit(c)) c = getchar(); ) + (a << ) + (c ^ ') , c = getchar(); return a; } ll w[MAXN] , v[MAXN] , num[MAXN] , allV[MAXN] , N , M , S , qj[MAXN][]; ll check(ll a){ ; i <= N ; i++){ num[i] = (w[i] >= a) + num[i - ]; allV[i] = (w[i] >= a ? v[i] : ) + allV[i - ]; } ; ; i <= M ; i++) sum += (num[qj[i][]] - num[qj[i][] - ]) * (allV[qj[i][]] - allV[qj[i][] - ]); return sum; } inline ll abss(ll a){ ? a : -a;} int main(){ , minW = 0x3f3f3f3f; N = read(); M = read(); S = read(); ; i <= N ; i++){ w[i] = read() , v[i] = read(); if(maxW < w[i]) maxW = w[i]; if(minW > w[i]) minW = w[i]; } ; i <= M ; i++) qj[i][] = read() , qj[i][] = read(); ){ ll mid = maxW + minW >> ; if(check(mid) >= S) minW = mid; else maxW = mid; } cout << min(abss(check(minW) - S) , abss(S - check(maxW))); ; }
*聪明的质检员
//每一次贪心地选择能够影响更多人的地方 #include<bits/stdc++.h> #define MAXN 1010 using namespace std; int far[MAXN] , down[MAXN] , D[MAXN] , maxD[MAXN] , minT[MAXN] , N , M , K; long long ans; inline void get(){ ; ; i <= N ; i++){ ans += time * down[i]; time = max(time , maxD[i]) + D[i]; } } inline void work(){ far[N] = N; ; i ; i--) far[i] = minT[i + ] > maxD[i + ] ? far[i + ] : i + ; , maxDir = ; ; i < N ; i++) if(D[i] && maxN < down[far[i]] - down[i]){ maxN = down[far[i]] - down[i]; maxDir = i; } D[maxDir]--; ans -= maxN; ; i <= far[maxDir] ; i++) minT[i] = max(minT[i - ] , maxD[i - ]) + D[i - ]; } int main(){ cin >> N >> M >> K; ; i < N ; i++) cin >> D[i]; ; i <= M ; i++){ int T , A , B; cin >> T >> A >> B; maxD[A] = max(maxD[A] , T); down[B]++; ans -= T; } get(); ; i <= N ; i++){ down[i] += down[i - ]; minT[i] = max(minT[i - ] , maxD[i - ]) + D[i - ]; } while(K--) work(); cout << ans; ; }
*观光公交
NOIP2012(clear)
//直接模拟 #include<bits/stdc++.h> #define ll long long using namespace std; inline ll fast_read() { char c = getchar(); ll a = ; ; while(!isdigit(c)) { ; c = getchar(); } ) + (a << ) + c - ' , c = getchar(); return k ? -a : a; } inline void fast_print(ll x) { ] , dirN = -; ) putchar('-') , x = -x; , x /= ; ) putchar('); ) putchar(num[dirN--] + ); putchar('\n'); } int main() { string a , b; cin >> a >> b; , la = a.size() , lb = b.size(); ; i < lb ; i++ , dirA++) { char c = a[dirA % la]; while(c != 'a' && c-- != 'A') { b[i]--; || b[i] == ) b[i] += ; } } cout << b; ; }
Vigenère 密码
//根据邻项交换推贪心策略，排序后算答案 #include<bits/stdc++.h> using namespace std; ] , allSum[] , maxN[]; struct p{ int l , r; }ans[]; bool cmp(p a , p b) { return a.l * a.r < b.l * b.r; } void comp() { ] < maxN[]) return; ] == maxN[]) ] ; i ; i--) if(d[i] < maxN[i]) return; else if(d[i] > maxN[i]) break; ; i <= d[] ; i++) maxN[i] = d[i]; } inline int fast_read() { char ch = getchar(); , k = ; while(!isdigit(ch)){ ; ch = getchar(); } ) + (a << ) + ch - ' , ch = getchar(); return a; } int main() { int n = fast_read(); ; i <= n ; i++) ans[i].l = fast_read() , ans[i].r = fast_read(); ].l) { allSum[++allSum[]] = ans[].l % ; ans[].l /= ; } sort(ans + , ans + n + , cmp); ; i <= n ; i++) { memset(d , , sizeof(d)); , sum = ; ] ; j ; j--) { sum = sum * + allSum[j]; if(sum >= ans[i].r) { d[j] = sum / ans[i].r; sum %= ans[i].r; if(!f) { f = ; d[] = j; } } } comp(); ; j <= allSum[] ; j++) allSum[j] *= ans[i].l; ; j <= allSum[] ; j++) ) { allSum[j + ] += allSum[j] / ; allSum[j] %= ; ]) allSum[]++; } } ] ; i ; i--) cout << maxN[i]; ; }
*国王游戏
//拓欧裸题 #include<bits/stdc++.h> #define ll long long using namespace std; inline ll fast_read() { char c = getchar(); ll a = ; ; while(!isdigit(c)) { ; c = getchar(); } ) + (a << ) + c - ' , c = getchar(); return k ? -a : a; } void exGcd(int a , int b , int &x , int &y) { ) x = / a , y = ; else { exGcd(b , a % b , x , y); int t = x; x = y; y = t - a / b * y; } } int main() { int a = fast_read() , b = fast_read() , c , d; exGcd(a , -b , c , d); ) c += b; cout << c % b; ; }
*同余方程
//线段树这种常数极大的东西在CCF老人机上一定会被卡常数成95pts #include<bits/stdc++.h> using namespace std; ]; inline int read(){ ; char c = getchar(); while(!isdigit(c)) c = getchar(); ) + (a << ) + (c ^ ') , c = getchar(); return a; } int cou , N; inline int min(int a , int b){ return a < b ? a : b; } struct node{ node *left , *right; int start , end , minN , minus_tag; node(){ if(_s == _e) minN = read(); else{ left = ); right = ) + , _e); minN = min(left->minN , right->minN); } } void change(int _s , int _e , int num){ if(_s == start && _e == end) ){ cout << - << endl << cou; exit(); } else{ minN += num; minus_tag += num; return; } left->minN += minus_tag; right->minN += minus_tag; left->minus_tag += minus_tag; right->minus_tag += minus_tag; minus_tag = ; ) left->change(_s , _e , num); ) right->change(_s , _e , num); else{ left->change(_s , start + end >> , num); right->change((start + end >> ) + , _e , num); } minN = min(left->minN , right->minN); } }*Tree; int main(){ int N = read() , K = read(); Tree = , N); ; cou <= K ; cou++) { int a = read() , b = read() , c = read(); Tree->change(b , c , -a); } cout << ; ; }
借教室
NOIP2013(clear)
//快速幂裸题 #include<bits/stdc++.h> #define ll long long using namespace std; inline ll fast_read() { char c = getchar(); ll a = ; ; while(!isdigit(c)) { ; c = getchar(); } ) + (a << ) + c - ' , c = getchar(); return k ? -a : a; } inline void fast_print(ll x) { ] , dirN = -; ) putchar('-') , x = -x; , x /= ; ) putchar('); ) putchar(num[dirN--] + ); } ] , circle; inline int fast_mi(int a) { ll num = % circle , add = ; while(a) { ) add = add * num % circle; a >>= ; num = num * num % circle; } return add; } int main() { int k = fast_read() , t = fast_read(); ]) { num[circle] = t; t = (num[circle++] + m) % n; } fast_print(num[fast_mi(k)]); ; }
转圈游戏
//离散化+逆序对（显然两个相对大小顺序一样的时候答案最优） #include<bits/stdc++.h> #define MAXN 100001 using namespace std; inline int read(){ ; char c = getchar(); while(!isdigit(c)) c = getchar(); ) + (a << ) + (c ^ ') , c = getchar(); return a; } int num1[MAXN] , num2[MAXN] , lsh1[MAXN] , lsh2[MAXN] , tree[MAXN] , N = read(); map < int , int > n1 , to2 , n2; inline ? a : -a;} inline int lowbit(int a){return a & -a;} inline int getSum(int a){ ; while(a){ sum += tree[a]; a -= lowbit(a); } return sum; } inline void add(int a){ while(a <= N){ tree[a]++; a += lowbit(a); } } int main(){ ; ; i < N ; i++) num1[i] = lsh1[i] = read(); ; i < N ; i++) num2[i] = lsh2[i] = read(); sort(lsh1 , lsh1 + N); ; i < N ; i++) n1[lsh1[i]] = i + ; ; i < N ; i++) to2[n1.find(num1[i])->second] = i + ; sort(lsh2 , lsh2 + N); ; i < N ; i++) n2[lsh2[i]] = i + ; ; i >= ; i--){ int t = to2.find(n2.find(num2[i])->second)->second; sum += getSum(t - ); add(t); } cout << sum % ; ; }
*火柴排队
//维护递增的单调栈 #include<bits/stdc++.h> #define ll long long using namespace std; inline ll fast_read() { char c = getchar(); ll a = ; ; while(!isdigit(c)) { ; c = getchar(); } ) + (a << ) + c - ' , c = getchar(); return k ? -a : a; } inline void fast_print(ll x) { ] , dirN = -; ) putchar('-') , x = -x; , x /= ; ) putchar('); ) putchar(num[dirN--] + ); } int sum , a; int main() { for(int n = fast_read() ; n ; n--) { int b = fast_read(); if(a > b) sum += a - b; a = b; } fast_print(sum + a); ; }
积木大赛
//DP #include<bits/stdc++.h> #define ll long long using namespace std; inline ll fast_read() { char c = getchar(); ll a = ; ; while(!isdigit(c)) { ; c = getchar(); } ) + (a << ) + c - ' , c = getchar(); return k ? -a : a; } inline void fast_print(ll x) { ] , dirN = -; ) putchar('-') , x = -x; , x /= ; ) putchar('); ) putchar(num[dirN--] + ); } ] , h2[]; int main() { , dir2 = ; h2[] = h1[] = fast_read(); ; i <= n ; i++) { int a = fast_read(); ) % == && h1[dir1] != a) h1[++dir1] = a; else h1[dir1] = a; ) % == && h2[dir2] != a) h2[++dir2] = a; else h2[dir2] = a; } fast_print(max(dir1 , dir2)); ; }
花匠
NOIP2014(clear)
//模拟 #include<bits/stdc++.h> using namespace std; ][] , Na[] , Nb[]; int main() { ios::sync_with_stdio(false); sf[][] = sf[][] = sf[][] = sf[][] = sf[][] = -; sf[][] = sf[][] = sf[][] = sf[][] = sf[][] = ; cin >> N >> a >> b; ; i < a ; i++) cin >> Na[i]; ; i < b ; i++) cin >> Nb[i]; while(N--) { if(Na[dirA] - Nb[dirB]) if(sf[Na[dirA]][Nb[dirB]]) ) sumA++; else sumB++; ) sumB++; else sumA++; dirA = (dirA + ) % a; dirB = (dirB + ) % b; } cout << sumA << " " << sumB; ; }
生活大爆炸版石头剪刀布
//一棵树上只有可能出现：爷爷和孙子（？）和同父兄弟这两种情况会产生联合权值，第二种权值的计算需要优化成O(n) #include<bits/stdc++.h> using namespace std; inline int read(){ register ; register char c = getchar(); while(!isdigit(c)) c = getchar(); ) + (a << ) + (c ^ ') , c = getchar(); return a; } inline int max(int a , int b){ return a > b ? a : b; } struct Edge{ int upEd , end; }now[]; ] , Las[]; ]; struct node{ int num , father , grandpa; }ans; int main(){ ; register ; ; i ^ n ; i++){ a = read(); b = read(); now[(i << ) - ].end = b; now[(i << ) - ].upEd = Las[a]; Las[a] = (i << ) - ; now[i << ].end = a; now[i << ].upEd = Las[b]; Las[b] = i << ; } ; i ^ n + ; i++) num[i] = read(); queue < node > q; ans.num = ; ans.father = ans.grandpa = ; q.push(ans); while(!q.empty()){ ans = q.front(); q.pop(); if(ans.grandpa){ sum += num[ans.grandpa] * num[ans.num] << ; maxN = max(maxN , num[ans.grandpa] * num[ans.num]); } vis[ans.num] = ; node ans1; ans1.grandpa = ans.father; ans1.father = ans.num; register , maxM2 = ; , sumN = ; for(register int i = Las[ans.num] ; i ; i = now[i].upEd) if(!vis[now[i].end]){ if(num[now[i].end] > maxM1){ maxM2 = maxM1; maxM1 = num[now[i].end]; } else if(num[now[i].end] > maxM2) maxM2 = num[now[i].end]; sumM += num[ans1.num = now[i].end]; sumN += num[now[i].end] * num[now[i].end]; q.push(ans1); } maxN = max(maxN , maxM1 * maxM2); sum += sumM * sumM - sumN; } printf(); ; }
*联合权值
//DP #include<bits/stdc++.h> using namespace std; inline int read(){ ; char c = getchar(); while(!isdigit(c)) c = getchar(); while(isdigit(c)){ a = (a << ) + (a << ) + (c ^ '); c = getchar(); } return a; } inline int min(int a , int b){ return a < b ? a : b; } struct gd{ int P , L , R; }now[]; bool cmp(gd a , gd b){ return a.P < b.P; } ][] , minN[][]; int main(){ ; cin >> N >> M >> K; ; i <= N ; i++){ jump[i][] = read(); jump[i][] = read(); } ; i <= K ; i++){ now[i].P = read(); now[i].L = read(); now[i].R = read(); } sort(now + , now + K + , cmp); ; i <= N ; i++){ memset(minN[i & ] , ])); ; j <= M ; j++) minN[i & ][j + jump[i][] > M ? M : j + jump[i][]] = min(minN[i & ][j + jump[i][] > M ? M : j + jump[i][]] , min(minN[i & ][j] , minN[i & ^ ][j]) + ); ] + ; j <= M ; j++) minN[i & ][j - jump[i][]] = min(minN[i & ][j - jump[i][]] , minN[i & ^ ][j]); if(now[dir].P == i){ ; j <= now[dir].L ; j++) minN[i & ][j] = 0x3f3f3f3f; for(int j = now[dir].R ; j <= M ; j++) minN[i & ][j] = 0x3f3f3f3f; ; ; j < now[dir].R && !f ; j++) ][j] != 0x3f3f3f3f) f = ; if(!f){ cout << << endl << dir - ; ; } dir++; } } int ans = 0x3f3f3f3f; ; i <= M ; i++) ans = min(ans , minN[N & ][i]); cout << << endl << ans; ; }
*飞扬的小鸟
//乱搞 #include<bits/stdc++.h> using namespace std; ][]; int main(){ ios::sync_with_stdio(false); , d , n; ; cin >> d >> n; ; i < n ; i++) { int a , b , c; cin >> a >> b >> c; m[a][b] = c; } ; i < ; i++) ; j < ; j++) { ; ) ; k <= i + d ; k++) ) ; p <= j + d ; p++) num += m[k][p]; if(num > maxN){ maxN = num; cou = ; } else if(num == maxN) cou++; } cout << cou << " " << maxN; ; }
无线网络发射器选址
//每一次预处理出无法到达终点的点并影响可以到达的点，然后最短路 #include<bits/stdc++.h> using namespace std; inline int read(){ ; char c = getchar(); while(!isdigit(c)) c = getchar(); ) + (a << ) + (c ^ ') , c = getchar(); return a; } vector < ] , FanEd[]; ] , vis2[]; int main(){ ios::sync_with_stdio();cin.tie();cout.tie(); int n = read() , m = read(); while(m--){ int a = read() , b = read(); Ed[a].push_back(b); FanEd[b].push_back(a); } ; i <= n ; i++) vis2[i] = ; int st = read() , end = read(); vis[end] = ; queue < int > q1; q1.push(end); while(!q1.empty()){ int t = q1.front(); q1.pop(); ; i ^ FanEd[t].size() ; i++) if(!vis[FanEd[t][i]]){ vis[FanEd[t][i]] = ; q1.push(FanEd[t][i]); } } ; i <= n ; i++) if(!vis[i]){ vis2[i] = ; ; j ^ FanEd[i].size() ; j++) vis2[FanEd[i][j]] = ; } if(!vis2[st]){ cout << -; ; } queue < pair < int , int > > q; q.push(make_pair(st , )); while(!q.empty()){ pair < int , int > t = q.front(); q.pop(); ; i ^ Ed[t.first].size() ; i++) if(vis2[Ed[t.first][i]]){ vis2[Ed[t.first][i]] = ; if(Ed[t.first][i] == end){ cout << t.second + ; ; } q.push(make_pair(Ed[t.first][i] , t.second + )); } } cout << -; ; }
寻找道路
//998244353真是个好质数 #include<bits/stdc++.h> #define MOD 998244353 #define ll long long using namespace std; inline ll read(){ ll a = ; char c = getchar(); ; while(!isdigit(c)){ if(c == '-') f = ; c = getchar(); } while(isdigit(c)){ a = ((a << ) + (a << ) + (c ^ ')) % MOD; c = getchar(); } return f ? -a : a; } ]; inline void print(int a){ ; while(a){ output[dirN++] = a % ; a /= ; } if(!dirN) putchar('); while(dirN) putchar(output[--dirN] + ); putchar('\n'); } ] , num[] , n , m; inline void calc(int dir){ ll sum = num[n]; ; i >= ; i--) sum = (sum * dir + num[i]) % MOD; if(!sum) ans[++ans[]] = dir; } int main(){ n = read(); m = read(); ; i <= n ; i++) num[i] = read(); ; i <= m ; i++) calc(i); ; i <= ans[] ; i++) print(ans[i]); ; }
*解方程
NOIP2015(clear)
//模拟 #include<bits/stdc++.h> using namespace std; ][]; int main() { int N; cin >> N; , j = + N / ; num[i][j] = ; ; k <= N * N ; k++) { && j == N) i++; ){ i = N; j++; } else if(j == N){ j = ; i--; }][j + ]){ i--; j++; } else i++; num[i][j] = k; } ; i <= N ; i++) { ; j <= N ; j++) cout << num[i][j] << " "; cout << endl; } ; }
神奇的幻方
//tarjan可以用来判环长哦！ //这下面是一个古老的Kosaraju #include<bits/stdc++.h> #define ll long long #define MAXN 200001 using namespace std; inline ll fast_read() { char c = getchar(); ll a = ; ; while(!isdigit(c)) { ; c = getchar(); } ) + (a << ) + c - ' , c = getchar(); return k ? -a : a; } inline void fast_print(ll x) { ] , dirN = -; ) putchar('-') , x = -x; , x /= ; ) putchar('); ) putchar(num[dirN--] + ); } int num[MAXN] , fanNum[MAXN] , zhan[MAXN] , minN = MAXN , N = fast_read() , dirZ; bool vis[MAXN]; struct edge{ int end , upEd; void init(int a , int b) { upEd = fanNum[a]; fanNum[a] = end = b; } }ans[MAXN]; void fanDfs(int k) { vis[k] = ; for(int i = fanNum[k] ; i ; i = ans[i].upEd) if(!vis[ans[i].end]) fanDfs(ans[i].end); zhan[dirZ++] = k; } int dfs(int k) { vis[k] = ; + dfs(num[k]); ; } int main() { ; i <= N ; i++) { num[i] = fast_read(); if(i == num[i]) { cout << ; ; } ans[i].init(num[i] , i); } ; i <= N ; i++) if(!vis[i]) fanDfs(i); memset(vis , , sizeof(vis)); ; dirZ--) if(!vis[zhan[dirZ]]) { int k = dfs(zhan[dirZ]); ) minN = min(minN , k); } fast_print(minN); ; }
信息传递
//搜顺子，散排直接DP #include<bits/stdc++.h> //This code is written by Itst using namespace std; inline int read(){ ; ; char c = getchar(); while(c != EOF && !isdigit(c)){ if(c == '-') f = ; c = getchar(); } while(c != EOF && isdigit(c)){ a = (a << ) + (a << ) + (c ^ '); c = getchar(); } return f ? -a : a; } ] , gui[] , dp[][][][][] , ans; inline void sub(int step){ ; ] = {}; ; i <= ; i++) ++num[pot[i]]; ] && gui[]){ ifGui = ; num[] += ; } else ] + gui[]) num[]++; ans = min(ans , dp[num[]][num[]][num[]][num[]][ifGui] + step); } void dfs(int now , int step){ if(step > ans) return; ){ sub(step); return; } && pot[now + ] >= ){ pot[now] -= ; ; && pot[i] >= ){ pot[i++] -= ; dfs(now , step + ); } while(--i >= now) pot[i] += ; } && pot[now + ] >= && pot[now + ] >= ){ pot[now] -= ; pot[now + ] -= ; ; && pot[i] >= ){ pot[i++] -= ; dfs(now , step + ); } while(--i >= now) pot[i] += ; } int i = now; while(pot[i]){ ) break; --pot[i++]; ) dfs(now , step + ); } while(--i >= now) ++pot[i]; dfs(now + , step); } void init_dp(){ ; m <= ; m++) ; k + m <= ; k++) ; j + k + m <= ; j++) ; i + j + k + m <= ; i++) ; i + j * + k * + m * <= && n <= && (n == || i >= ) ; n++) if(i + j + k + m){ ] = {i , j , k , m}; if(n) dp[i][j][k][m][n] = min(dp[i][j][k][m][n] , dp[i - ][j][k][m][]); if(m){ --num[]; ; p <= ; p++) if(num[p]){ --num[p]; if(p) ++num[p - ]; ; q <= ; q++) if(num[q]){ --num[q]; if(q) ++num[q - ]; dp[i][j][k][m][n] = min(dp[i][j][k][m][n] , dp[num[]][num[]][num[]][num[]][num[] >= && n]); if(q) --num[q - ]; ++num[q]; } ++num[p]; if(p) --num[p - ]; } ; p <= ; p++) if(num[p]){ --num[p]; ) ++num[p - ]; ; q <= ; q++) if(num[q]){ --num[q]; ) ++num[q - ]; dp[i][j][k][m][n] = min(dp[i][j][k][m][n] , dp[num[]][num[]][num[]][num[]][num[] >= && n]); ) --num[q - ]; ++num[q]; } ++num[p]; ) --num[p - ]; } ++num[]; } ; a <= ; a++) if(num[a]){ --num[a]; ) ++num[]; ; p <= ; p++) if(num[p]){ --num[p]; if(p) ++num[p - ]; dp[i][j][k][m][n] = min(dp[i][j][k][m][n] , dp[num[]][num[]][num[]][num[]][num[] >= && n]); if(p) --num[p - ]; ++num[p]; } ; p <= ; p++) if(num[p]){ --num[p]; ) ++num[p - ]; dp[i][j][k][m][n] = min(dp[i][j][k][m][n] , dp[num[]][num[]][num[]][num[]][num[] >= && n]); ++num[p]; ) --num[p - ]; } ) --num[]; ++num[a]; } ; p ; p--) ; q <= ; ++q) if(num[q]){ --num[q]; if(q >= p) ++num[q - p]; dp[i][j][k][m][n] = min(dp[i][j][k][m][n] , dp[num[]][num[]][num[]][num[]][num[] >= && n]); if(q >= p) --num[q - p]; ++num[q]; } ++dp[i][j][k][m][n]; } } int main(){ #ifdef LG freopen("2668.in" , "r" , stdin); //freopen("2668.out" , "w" , stdout); #endif memset(dp , 0x3f , sizeof(dp)); dp[][][][][] = ; init_dp(); int T = read() , N = read(); ; i <= T ; i++){ memset(pot , , sizeof(pot)); gui[] = gui[] = ; ans = 0x7fffffff; ; j <= N ; j++){ int a = read(); if(a){ ++pot[a <= ? a + : a - ]; read(); } else ++gui[read()]; } dfs( , ); printf("%d\n" , ans); } ; }
*斗地主
//二分+贪心 #include<bits/stdc++.h> #define ll long long using namespace std; inline ll fast_read() { char c = getchar(); ll a = ; ; while(!isdigit(c)) { ; c = getchar(); } ) + (a << ) + c - ' , c = getchar(); return k ? -a : a; } inline void fast_print(ll x) { ] , dirN = -; ) putchar('-') , x = -x; , x /= ; ) putchar('); ) putchar(num[dirN--] + ); } ]; int main() { , t = L + ; num[M + ] = L; ; i <= M ; i++) num[i] = fast_read(); ) { , cou = , befL = ; ; i <= M + ; i++) if(num[i] - befL < mid) cou++; else befL = num[i]; if(cou > N) t = mid; else h = mid; } fast_print(h); ; }
跳石头
//DP #include<bits/stdc++.h> #define MOD 1000000007 using namespace std; ][][]; vector < ]; int main(){ int N , M , K; string s , cmp; cin >> N >> M >> K >> s >> cmp; bp[][][] = ; ; i >= ; i--) v[cmp[i] - 'a'].push_back(i); ; i < N ; i++){ ; j <= M ; j++) ; k <= K ; k++) bp[][j][k] = (bp[][j][k] + bp[][j][k]) % MOD; memcpy(bp[] , bp[] , ])); memset(bp[] , , ])); ; j < v[s[i] - 'a'].size() ; j++) for(int k = K ; k ; k--) bp[][v[s[i] - ][k] = ((bp[][v[s[i] - ][v[s[i] - ]) % MOD + bp[][v[s[i] - ]) % MOD; } cout << ((bp[][M][K] + bp[][M][K]) % MOD + bp[][M][K]) % MOD; ; }
子串
//删掉一条边的影响一定只会在前i条路径上（i极大），所以从大到小在树上加边，每一次找到在所有最长的路径上的边中权值最大的边尝试删除。 #include<bits/stdc++.h> #define MAXN 300002 #define l(x) Tree[x].l #define r(x) Tree[x].r #define sum(x) Tree[x].sum #define mark(x) Tree[x].mark #define mid(x) (Tree[x].l + Tree[x].r >> 1) #define maxMark(dir) Tree[dir].maxMark #define maxNum(dir) Tree[dir].maxNum using namespace std; struct node{ int l , r , sum , mark , maxMark , maxNum; }Tree[MAXN << ]; struct Edge{ int end , w , upEd; }Ed[MAXN << ]; struct route{ int start , end , w; }Now[MAXN]; int head[MAXN] , val[MAXN] , size[MAXN] , fa[MAXN] , son[MAXN] , dep[MAXN]; int N , M , cntEd , ts , top[MAXN] , ind[MAXN] , rk[MAXN]; bool cmp(route a , route b){ return a.w > b.w; } inline int max(int a , int b){ return a > b ? a : b; } inline void addEd(int a , int b , int c){ Ed[++cntEd].end = b; Ed[cntEd].w = c; Ed[cntEd].upEd = head[a]; head[a] = cntEd; } void dfs1(int dir , int father , int v){ val[dir] = v; size[dir] = ; dep[dir] = dep[fa[dir] = father] + ; for(int i = head[dir] ; i ; i = Ed[i].upEd) if(fa[dir] != Ed[i].end){ dfs1(Ed[i].end , dir , Ed[i].w); size[dir] += size[Ed[i].end]; if(size[son[dir]] < size[Ed[i].end]) son[dir] = Ed[i].end; } } void dfs2(int dir , int t){ top[dir] = t; rk[ind[dir] = ++ts] = dir; if(!son[dir]) return; dfs2(son[dir] , t); for(int i = head[dir] ; i ; i = Ed[i].upEd) if(Ed[i].end != son[dir] && Ed[i].end != fa[dir]) dfs2(Ed[i].end , Ed[i].end); } inline void pushup(int dir , int maxN){ ) , maxMark(dir << | ))) maxNum(dir) = max(maxNum(dir) , maxN); else{ maxMark(dir) = max(maxMark(dir << ) , maxMark(dir << | )); maxNum(dir) = maxN; } } inline void pushdown(int dir){ mark(dir << ) += mark(dir); mark(dir << | ) += mark(dir); maxMark(dir << ) += mark(dir); maxMark(dir << | ) += mark(dir); mark(dir) = ; } void init(int l , int r , int dir){ l(dir) = l; r(dir) = r; if(l == r) sum(dir) = maxNum(dir) = val[rk[l]]; else{ init(l , mid(dir) , dir << ); init(mid(dir) + , r , dir << | ); sum(dir) = sum(dir << ) + sum(dir << | ); maxNum(dir) = max(maxNum(dir << ) , maxNum(dir << | )); } } int getSum(int l , int r , int dir){ if(l(dir) >= l && r(dir) <= r) return sum(dir); ; if(l <= mid(dir)) sum += getSum(l , r , dir << ); if(r > mid(dir)) sum += getSum(l , r , dir << | ); return sum; } int getMark(int l , int r , int dir , int now){ if(l(dir) >= l && r(dir) <= r){ mark(dir)++; ; } pushdown(dir); ; if(l <= mid(dir)) maxN = max(maxN , getMark(l , r , dir << , now)); if(r > mid(dir)) maxN = max(maxN , getMark(l , r , dir << | , now)); if(maxN) pushup(dir , maxN); return maxN; } inline void work1(int dir){ int x = Now[dir].start , y = Now[dir].end , tx = top[x] , ty = top[y]; while(tx != ty) if(dep[tx] >= dep[ty]){ Now[dir].w += getSum(ind[tx] , ind[x] , ); x = fa[tx]; tx = top[x]; } else{ Now[dir].w += getSum(ind[ty] , ind[y] , ); y = fa[ty]; ty = top[y]; } if(ind[x] < ind[y]) Now[dir].w += getSum(ind[x] + , ind[y] , ); if(ind[x] > ind[y]) Now[dir].w += getSum(ind[y] + , ind[x] , ); } inline int work2(int dir){ ; while(tx != ty) if(dep[tx] >= dep[ty]){ maxN = max(maxN , getMark(ind[tx] , ind[x] , , dir)); x = fa[tx]; tx = top[x]; } else{ maxN = max(maxN , getMark(ind[ty] , ind[y] , , dir)); y = fa[ty]; ty = top[y]; } if(ind[x] < ind[y]) maxN = max(maxN , getMark(ind[x] + , ind[y] , , dir)); if(ind[x] > ind[y]) maxN = max(maxN , getMark(ind[y] + , ind[x] , , dir)); return maxN; } int main(){ srand((unsigned)time()); scanf("%d%d" , &N , &M); ; i < N ; i++){ int a , b , c; scanf("%d%d%d" , &a , &b , &c); addEd(a , b , c); addEd(b , a , c); } ; dfs1(S , , ); dfs2(S , S); init( , N , ); ; i <= M ; i++){ scanf("%d%d" , &Now[i].start , &Now[i].end); work1(i); } sort(Now + , Now + M + , cmp); , minN = ; while(dir <= M){ int t = work2(dir); ].w <= Now[].w - t){ minN = min(minN , Now[].w - t); break; } minN = Now[dir + ].w; dir++; } cout << minN; ; }
*运输计划
NOIP2016(clear)
//有点绕的模拟 #include<bits/stdc++.h> using namespace std; ]; ]; int main() { ios::sync_with_stdio(false); ; cin >> n >> m; ; i < n ; i++) cin >> cx[i] >> name[i]; while(m) { int a , b; cin >> a >> b; ) dir = (dir + b) % n; else dir = (dir - b + n) % n; m--; } cout << name[dir]; ; }
玩具谜题
//期望DP #include<bits/stdc++.h> #define MAXN 2001 using namespace std; ] , gl[MAXN]; ] , route[][] , n , m , v , e; inline double calc(int dir , bool f1 , bool f2){ ; ; i <= f1 ; i++) ; j <= f2 ; j++) sum += route[room[dir - ][i]][room[dir][j]] * (f1 ? (i ? gl[dir - ] : - gl[dir - ]) : ) * (f2 ? (j ? gl[dir] : - gl[dir]) : ); return sum; } int main(){ ios::sync_with_stdio(); cin.tie(); cout.tie(); cin >> n >> m >> v >> e; ){ cout << ) << 0.00; ; } ; i <= n ; i++) cin >> room[i][]; ; i <= n ; i++) cin >> room[i][]; ; i <= n ; i++) cin >> gl[i]; memset(route , 0x3f , sizeof(route)); while(e--){ int a , b , c; cin >> a >> b >> c; route[a][b] = route[b][a] = min(route[a][b] , c); } ; k <= v ; k++){ route[k][k] = ; ; i <= v ; i++) ; j <= v ; j++) route[i][j] = min(route[i][j] , route[i][k] + route[k][j]); } double minN = 0x7fffffff; memset(minQW , 0x7f , sizeof(minQW)); minQW[][] = minQW[][] = ; ; i <= n ; i++){ ; j--){ minQW[j][] = min(minQW[j][] + calc(i , , ) , minQW[j][] + calc(i , , )); if(j) minQW[j][] = min(minQW[j - ][] + calc(i , , ) , minQW[j - ][] + calc(i , , )); } } ; i <= m ; i++) minN = min(minN , min(minQW[i][] , minQW[i][])); cout << ) << minN; ; }
*换教室
//组合数+二维前缀和 #include<bits/stdc++.h> using namespace std; ][] , all[][]; int main(){ ios::sync_with_stdio(); int t , k; cin >> t >> k; ; i <= ; i++) ; j <= i ; j++) { || j == i) num[i][j] = ; ][j] + num[i - ][j - ]) % k; ; } ; i <= ; i++) ; j <= ; j++) all[i][j] += all[i][j - ]; ; i <= ; i++) ; j <= ; j++) all[i][j] += all[i - ][j]; while(t--){ int a , b; cin >> a >> b; cout << all[a][b] << endl; } ; }
组合数问题
//队列优化堆 #include<bits/stdc++.h> using namespace std; , inf = << ; ][MAXN] , n , m , u , v , q , t , hd[] , tl[]; inline int top(){ ; ; i < ; i++) if(hd[i] != tl[i] && qq[i][hd[i]] > maxN){ maxN = qq[i][hd[i]]; dir = i; } ) hd[dir]++; return maxN; } inline void insert(int dir , int num){ qq[dir][tl[dir]++] = num; } inline bool cmp(int a , int b){ return a > b; } int main(){ cin >> n >> m >> q >> u >> v >> t; ; i < n ; i++) cin >> qq[][i]; tl[] = n; sort(qq[] , qq[] + n , cmp); ; i <= m ; i++){ ) * q; ) cout << k << ' '; int x = (long long)k * u / v; insert( , x - i * q); insert( , k - x - i * q); } cout << endl; ; while(k != -inf){ cnt++; ) cout << k + m * q << ' '; k = top(); } ; }
蚯蚓
//状压DP #include<bits/stdc++.h> #define eps 1e-12 using namespace std; inline int min(int a , int b){return a < b ? a : b;} ] , y[]; << ] , N , pwx[] , numPWX; inline void init(){ ; i < N ; i++){ ; ; j < N ; j++){ if(x[i] >= x[j] - eps && x[i] <= x[j] + eps) continue; ; ; k <= numPWX && ff ; k++) << i) | ( << j))) == (( << i) | ( << j))) ff = ; if(!ff) continue; double a = (y[i] * x[j] - x[i] * y[j]) / x[i] / x[j] / (x[i] - x[j]); if(a > -eps) continue; double b = (y[i] - a * x[i] * x[i]) / x[i]; << i) | ( << j); ; k < N ; k++) if(a * x[k] * x[k] + b * x[k] >= y[k] - eps && a * x[k] * x[k] + b * x[k] <= y[k] + eps) t |= << k; pwx[++numPWX] = t; f = ; } if(!f){ ; ; j <= numPWX && ff ; j++) << i)) == ( << i)) ff = ; if(ff) pwx[++numPWX] = << i; } } } int main(){ int T , m; for(scanf("%d" , &T) ; T ; T--){ numPWX = ; minN[] = ; scanf("%d%d" , &N , &m); memset(minN , , << N)); minN[] = ; ; i < N ; i++) scanf("%lf %lf" , x + i , y + i); init(); ; i < ( << N) - ; i++) if(minN[i] < N) ; j <= numPWX ; j++) minN[i | pwx[j]] = min(minN[i | pwx[j]] , minN[i] + ); printf( << N) - ]); } ; }
*愤怒的小鸟
//树上差分+线段树合并 #include<bits/stdc++.h> #define mid ((l + r) >> 1) //This code is written by Itst using namespace std; inline int read(){ ; ; char c = getchar(); while(c != EOF && !isdigit(c)){ if(c == '-') f = ; c = getchar(); } while(c != EOF && isdigit(c)){ a = (a << ) + (a << ) + (c ^ '); c = getchar(); } return f ? -a : a; } ; struct Edge{ int end , upEd; }Ed[MAXN * ]; struct query{ int from , to , val; }q1[MAXN] , q2[MAXN]; struct node{ int l , r , val; }Tree[MAXN * ]; ] , root[MAXN] , times[MAXN] , ans[MAXN] , cntNode , N , M , cntEd; inline void addEd(int a , int b){ Ed[++cntEd].end = b; Ed[cntEd].upEd = head[a]; head[a] = cntEd; } inline void pushup(int now){ Tree[now].val = Tree[Tree[now].l].val + Tree[Tree[now].r].val; } void insert(int& now , int l , int r , int tar , int val){ if(!now){ now = ++cntNode; Tree[now].l = Tree[now].r = Tree[now].val = ; } if(l == r){ Tree[now].val += val; return; } if(mid >= tar) insert(Tree[now].l , l , mid , tar , val); else insert(Tree[now].r , mid + , r , tar , val); pushup(now); } int query(int now , int l , int r , int tar){ if(!Tree[now].val) ; if(l == r) return Tree[now].val; if(mid >= tar) return query(Tree[now].l , l , mid , tar); , r , tar); } int merge(int p , int q){ if(!p) return q; if(!q) return p; Tree[p].val += Tree[q].val; Tree[p].l = merge(Tree[p].l , Tree[q].l); Tree[p].r = merge(Tree[p].r , Tree[q].r); return p; } void dfs(int now , int fa){ dep[now] = dep[fa] + ; jump[now][] = fa; ; i < ; i++) jump[now][i] = jump[jump[now][i - ]][i - ]; for(int i = head[now] ; i ; i = Ed[i].upEd) if(Ed[i].end != fa) dfs(Ed[i].end , now); } int jumpToLCA(int x , int y){ if(dep[x] < dep[y]) swap(x , y); ; i >= ; i--) << i) >= dep[y]) x = jump[x][i]; if(x == y) return x; ; i >= ; i--) if(jump[x][i] != jump[y][i]){ x = jump[x][i]; y = jump[y][i]; } ]; } int jumpToCH(int x , int y){ ; i >= ; i--) if(jump[x][i] != y) x = jump[x][i]; return x; } void Dfs(int now){ for(int i = head[now] ; i ; i = Ed[i].upEd) ]){ Dfs(Ed[i].end); root[now] = merge(root[now] , root[Ed[i].end]); } ans[now] += query(root[now] , , N << , times[now] + dep[now]); } void DFS(int now){ for(int i = head[now] ; i ; i = Ed[i].upEd) ]){ DFS(Ed[i].end); root[now] = merge(root[now] , root[Ed[i].end]); } ans[now] += query(root[now] , -N , N , times[now] - dep[now]); } int main(){ #ifdef OJ freopen("1600.in" , "r" , stdin); //freopen("1600.out" , "w" , stdout); #endif N = read(); M = read(); ; i < N ; i++){ int a = read() , b = read(); addEd(a , b); addEd(b , a); } ; i <= N ; i++) times[i] = read(); dfs( , ); ; i <= M ; i++){ int a = read() , b = read() , t = jumpToLCA(a , b); q1[i].from = a; q1[i].to = t; q1[i].val = dep[a]; q2[i].from = b; q2[i].to = jump[t][]; q2[i].val = dep[a] - (dep[t] << ); } ; i <= M ; i++){ insert(root[q1[i]. , N << , q1[i].val , ); insert(root[q1[i].to] , , N << , q1[i].val , -); } Dfs(); cntNode = ; memset(root , , sizeof(root)); ; i <= M ; i++){ insert(root[q2[i].); insert(root[q2[i].to] , -N , N , q2[i].val , -); } DFS(); ; i <= N ; i++) printf("%d " , ans[i]); ; }
*天天爱跑步
NOIP2017(clear)
//小学奥数结论题了解一下 #include<bits/stdc++.h> using namespace std; int main() { unsigned long long a , b; cin >> a >> b; cout << a * b - a - b; ; }
小凯的疑惑
//比较清爽的大模拟 #include<bits/stdc++.h> //This code is written by Itst using namespace std; inline int read(){ ; ; char c = getchar(); while(c != EOF && !isdigit(c)){ if(c == '-') f = ; c = getchar(); } while(c != EOF && isdigit(c)){ a = (a << ) + (a << ) + (c ^ '); c = getchar(); } return f ? -a : a; } inline bool getF(){ char c = getchar(); while(!isupper(c)) c = getchar(); return c == 'F'; } ]; map < int , string > m; set < string > h; bool cmp(string l , string r){ if(r == "n") ; if(l == "n" && r != "n") ; if(l.size() != r.size()) return l.size() > r.size(); ; i < l.size() ; i++) if(l[i] != r[i]) return l[i] > r[i]; ; } int main(){ #ifdef LG freopen("3952.in" , "r" , stdin); //freopen("3952.out" , "w" , stdout); #endif for(int T = read() ; T ; --T){ h.clear(); , maxN = , top = , now = ; ; char c = getchar(); ') c = getchar(); if(c == 'n') pw = read(); ; i <= L ; i++) if(getF()){ string s , l , r; cin >> s >> l >> r; if(h.count(s)) ifERR = ; else{ h.insert(s); m[top + ] = s; if(cmp(l , r)) st[++top] = -; else if(r == "n" && l != "n") st[++top] = ; else st[++top] = ; now += st[top]; maxN = max(maxN , now); } } else if(!top) ifERR = ; else{ now -= st[top]; h.erase(m.find(top--)->second); } if(top || ifERR) puts("ERR"); else puts(pw == maxN ? "Yes" : "No"); } ; }
时间复杂度
//最短路+记搜 #include<bits/stdc++.h> #define int long long #define MAXN 100010 using namespace std; inline int read(){ ; ; char c = getchar(); while(!isdigit(c)){ if(c == '-') f = ; c = getchar(); } while(isdigit(c)){ a = (a << ) + (a << ) + (c ^ '); c = getchar(); } return f ? -a : a; } struct Edge{ int end , upEd , w; }Ed[MAXN << ] , fanEd[MAXN << ]; ] , minDis[MAXN] , fanHead[MAXN] , head[MAXN] , N , K , cntEd , cntFanEd , P; priority_queue < pair < int , int > > q; ]; inline void addEd(int a , int b , int c){ Ed[++cntEd].end = b; Ed[cntEd].upEd = head[a]; Ed[cntEd].w = c; head[a] = cntEd; } inline void addFanEd(int a , int b , int c){ fanEd[++cntFanEd].end = b; fanEd[cntFanEd].upEd = fanHead[a]; fanEd[cntFanEd].w = c; fanHead[a] = cntFanEd; } int dfs(int now , int sub){ if(sub > K) ; if(vis[now][sub]) ; ) return ans[now][sub]; ans[now][sub] = ; vis[now][sub] = ; for(int i = head[now] ; i ; i = Ed[i].upEd){ int t = dfs(Ed[i].end , minDis[Ed[i].end] + Ed[i].w - minDis[now] + sub); ) ; else ans[now][sub] = (ans[now][sub] + t) % P; } vis[now][sub] = ; if(now == N) ans[now][sub]++; return ans[now][sub]; } void Dijk(){ memset(minDis , 0x3f , sizeof(minDis)); minDis[N] = ; q.push(make_pair( , N)); while(!q.empty()){ pair < int , int > t = q.top(); q.pop(); if(-t.first > minDis[t.second]) continue; for(int i = fanHead[t.second] ; i ; i = fanEd[i].upEd) if(minDis[fanEd[i].end] > minDis[t.second] + fanEd[i].w){ minDis[fanEd[i].end] = minDis[t.second] + fanEd[i].w; q.push(make_pair(-minDis[fanEd[i].end] , fanEd[i].end)); } } } main(){ for(int T = read() ; T ; T--){ N = read(); int M = read(); K = read(); P = read(); memset(fanHead , , sizeof(fanHead)); memset(head , , sizeof(head)); memset(ans , - , sizeof(ans)); memset(vis , , sizeof(vis)); cntEd = cntFanEd = ; while(M--){ int a = read() , b = read() , c = read(); addEd(a , b , c); addFanEd(b , a , c); } Dijk(); cout << dfs( , ) << endl; } ; }
*逛公园
//记忆化搜索 #include<bits/stdc++.h> #define MAXN 1001 #define dou double using namespace std; ] , v[MAXN] , T; dou mm[MAXN][MAXN]; dou dis(dou x1 , dou x2 , dou y1 , dou y2 , dou z1 , dou z2) { return sqrt((x1 - x2) * (x1 - x2) +(y1 - y2) * (y1 - y2) +(z1 - z2) * (z1 - z2)); } bool sr(int m) { v[m] = ; ; ] + r >= h) o = ; ; i <= n && !o ; i++) if(i != m && !v[i]) { if(!mm[i][m]) mm[m][i] = dis(p[i][] , p[m][] , p[i][] , p[m][] , p[i][] , p[m][]); else continue; * r) o = sr(i); } return o; } int main() { ios::sync_with_stdio(false); ; for(cin >> T ; T ; T--) { cin >> n >> h >> r; ; i <= n ; i++) { cin >> p[i][] >> p[i][] >> p[i][]; v[i] = ; ; j <= n ; j++) mm[i][j] = ; } ; ; i <= n && !o ; i++) ] - r <= ) o = sr(i); cout << (b ? "\n" : "") << (o ? "Yes" : "No"); b = ; } ; }
奶酪
//拆点Splay->动态开点线段树 // luogu-judger-enable-o2 #include<bits/stdc++.h> #define int long long using namespace std; inline int read(){ ; char c = getchar(); while(!isdigit(c)) c = getchar(); while(isdigit(c)){ a = (a << ) + (a << ) + (c ^ '); c = getchar(); } return a; } ; struct node{ ]; }Tree[]; ] , rootBef[MAXN + ] , rootBeh[MAXN + ]; inline int create(int l , int r , bool f){ int t = ++cntNode; Tree[t].l = l; Tree[t].r = r; if(f) Tree[t].size = r - l + ; return t; } inline void split(int now , bool f){ Tree[now].ch[] = create(Tree[now].l , Tree[now].r + Tree[now].l >> , f); Tree[now].ch[] = create(Tree[now].l + Tree[now].r + >> , Tree[now].r , f); } int findKth(int now , int k , bool f){ Tree[now].size--; if(Tree[now].l == Tree[now].r) return f ? Tree[now].val : Tree[now].l; ] && !Tree[now].ch[]) split(now , ); ]].size < k) ] , k - Tree[Tree[now].ch[]].size , f); ] , k , f); } void insert(int now , int tar , int k){ Tree[now].size++; if(Tree[now].l == Tree[now].r){ Tree[now].val = k; return; } ]) split(now , ); ]].r) insert(Tree[now].ch[] , tar , k); else insert(Tree[now].ch[] , tar , k); } signed main(){ N = read(); M = read(); Q = read(); ; i <= N ; i++){ rootBef[i] = create( , M - , ); rootBeh[i] = create( , Q , ); } rootBef[N + ] = create( , N , ); rootBeh[N + ] = create( , Q , ); ; i <= N ; i++) insert(rootBef[N + ] , i , i * M); ; i <= Q ; i++){ int a = read() , b = read() , t; if(b == M) t = Tree[rootBef[N + ]].size >= a ? findKth(rootBef[N + ] , a , ) : findKth(rootBeh[N + ] , a - Tree[rootBef[N + ]].size , ); else{ t = Tree[rootBef[a]].size >= b ? findKth(rootBef[a] , b , ) + (a - ) * M : findKth(rootBeh[a] , b - Tree[rootBef[a]].size , ); insert(rootBeh[a] , ++cnt[a] , Tree[rootBef[N + ]].size >= a ? findKth(rootBef[N + ] , a , ) : findKth(rootBeh[N + ] , a - Tree[rootBef[N + ]].size , )); } printf("%lld\n" , t); insert(rootBeh[N + ] , i , t); } ; }
*列队
