可能没很多人看，后面没写思路，有问题单独问我吧

目录

7-1 区间翻转

7-2 次大值的和

7-3 买东西

7-4 双重子串

7-5 对决

7-6 最大公约数

7-7 填数字

7-8 放小球

7-9 给树染色

7-10 摆放小球

7-11 区间的个数

7-12 选零食

7-13 小球之间的距离

7-14 1还是2

7-15 青春猪头之我没学过C语言

7-16 打怪兽

7-17 背上书包去旅行

7-18 向前走

7-19 热水器

7-20 走方格

7-21 朋友圈

7-22 走方格

7-23 和与积

7-24 增加硬币

7-25 日落大道

7-26 ICPC保定站

7-27 简单的异或

7-28 选我啊！

7-29 豪华酒店

7-30 摆放小球

7-31 最大公约数的和

7-32 一道简单题

7-33 一个无限大的集合

7-1 区间翻转

思路：

贪心，我们每次操作，除最后是这种“RRRRRL” 或 “LRRRR” 操作后只能使满意度+1的特殊情况外，总能使满意度+2.

代码：

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int N = 200010, M = N * 2;
int n, m, r1, r2;
string s;
int main() {cin >> n >> m;getchar();cin >> s;int res = 0;for (int i = 0; i < n - 1; i++) {if (s[i] == s[i + 1])res++;}res = min(res + m * 2, n - 1);cout << res;return 0;}

7-2 次大值的和

思路：

计算每一个值的对结果的贡献。即它作为次大值出现是什么情况。

即左边出现一个比他大的值&&右边没有比他大的值，或者对称情况

这里要用单调栈来算每个数左边距离其最近的比它大的数，右边同理，最后将这些情况的结果计算出来，详见代码。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
int n;
int a[N],b[N];
int l_low[N], l_up[N], r_low[N], r_up[N];
long long res;
int stk1[N], stk2[N], tt;
int main() {scanf("%d", &n);for (int i = 1; i <= n; i++) {scanf("%d", &a[i]);b[a[i]] = i;}for (int i = 1; i <= n; i++) {while (tt && a[stk1[tt]] < a[i])tt--;if (!tt) {l_low[i] = 1;l_up[i] = -1;}else {l_low[i] = stk1[tt] + 1;l_up[i] = stk1[tt];}stk1[++tt] = i;}tt = 0;for (int i = n; i >= 1; i--) {while (tt && a[stk2[tt]] < a[i])tt--;//cout << tt << " " << stk2[tt] << endl;if (!tt) {r_low[i] = n;r_up[i] = -1;}else {r_low[i] = stk2[tt] - 1;r_up[i] = stk2[tt];}stk2[++tt] = i;}for (int i = 1; i <= n; i++) {int llow = i - l_low[i];int rlow = r_low[i] - i;int lup, rup;if (l_up[i] == -1) {lup = 0;}else {lup = 1;while (--l_up[i] && a[i] > a[l_up[i]])lup++;}if (r_up[i] == -1) {rup = 0;}else {rup = 1;while (++r_up[i] != n + 1 && a[i] > a[r_up[i]])rup++;}//cout << llow << " " << lup << " " << rlow << " " << rup << endl;res += ((long long)(llow + 1) * rup + (long long)(rlow + 1)  * lup) * a[i];}cout << res;return 0;
}

7-3 买东西

思路：

贪心：每次用一张券使得最贵的物品价格除以2

代码：

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int N = 100010, M = N * 2, mod = 1e9 + 7;
int n, m;
priority_queue<int> q;int main() {cin >> n >> m;for (int i = 0; i < n; i++) {int x;cin >> x;q.push(x);}while (m--) {int x = q.top();if (x == 0)break;q.pop();q.push(x / 2);}LL sum = 0;while (!q.empty()) {sum += q.top();q.pop();}cout << sum;
}

7-4 双重子串

simple 里有

7-5 对决

思路：

将某两个人的比赛看成一个节点，因为每个人都要按已有的顺序比赛，所以给每个人先比的比赛到后比的比赛建一条边，然后做一遍关键路径 ，即完成所有任务所需要的最长时间。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int N = 1e6+10, M = 1e6+10, mod = 1e9 + 7;
int n, m, x;
map<PII, int> mp;
int h[N], e[M], ne[M], idx;
int d[M],f[M];
int cnt;
void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int get(int a, int b) {if (a > b)swap(a, b);if (mp.count(make_pair(a,b)) == 0)mp[make_pair(a, b)] = ++cnt;return mp[{a, b}];
}int main()
{cin >> n;memset(h, -1, sizeof h);for (int i = 1; i <= n; i++) {cin >> x;int lst = get(i, x);for (int j = 1; j <= n - 2; j++) {cin >> x;x = get(i, x);add(lst, x);d[x]++;lst = x;}}queue<int> q;for (int i = 1; i <= n * (n - 1) / 2; i++)if (!d[i])q.push(i),f[i] = 1;int res = 0;while (q.size()) {int t = q.front();q.pop();res++;for (int i = h[t]; ~i; i = ne[i]) {int j = e[i];if (--d[j] == 0)q.push(j);f[j] = max(f[j], f[t] + 1);}}if (res != (n - 1) * n / 2)puts("-1");else {int num = 0;for (int i = 1; i <= (n - 1) * n / 2; i++)num = max(num, f[i]);cout << num;}return 0;
}

7-6 最大公约数

思路：

这题有个结论：最大公约数一定是数组求和的一个约数

做法：

数组求和sum，计算每个约数能不能满足要求（看看能不能在m次操作内把这个数组变为全0）

代码：

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int N = 200010, M = N * 2, mod = 1e9 + 7;
int n, m;
int a[N],b[N];
int sum;bool check(int x) {int s = 0,t = 0;for (int i = 0; i < n; i++) {b[i] = a[i] % x;s += b[i];}if (s % x != 0)return false;t = s / x;sort(b, b + n);for (int i = n - 1; t ; i--,t--) {s -= b[i];}if (s <= m)return true;else return false;
}int main() {cin >> n >> m;for (int i = 0; i < n; i++) {cin >> a[i];sum += a[i];}int res = 0;for (int i = 1; i <= sum / i; i++) {if (sum % i == 0) {if (check(i))res = max(res, i);if (check(sum / i))res = max(res, sum / i);}}cout << res;
}

7-7 填数字

思路：

DP f[i][j] 表示前i位数，对13取模余j的方案数

初始化第一位，如果是问号，初始化0~9，否则是几就初始化几

转移方程： f[i][(j * 10 + s[i] - '0') % 13] +=  f[i - 1][j] ;

思考一个点：19对13取余得6 ， 192对13取余 等价于19对13取余的结果6 乘10 再加 2 再对13取余

代码：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10,mod = 1e9 + 7;
int n;
int f[N][13];
int main()
{string s;cin>>s;s = " " + s;if(s[1] == '?'){for(int i=0;i<10;i++)f[1][i] = 1;}else f[1][s[1] - '0'] = 1;for(int i = 2;i < s.size();i++){bool fg = (s[i] == '?');for(int j = 0;j < 13;j++){if(f[i - 1][j]){if(fg){for(int k = 0;k < 10;k ++){f[i][(j*10 + k) % 13] = (f[i][(j*10 + k) % 13] + f[i - 1][j]) % mod;}}else f[i][(j * 10 + s[i] - '0') % 13] = (f[i][(j * 10 + s[i] - '0') % 13] + f[i - 1][j]) %mod;}}}cout<<f[s.size() - 1][5];
}

7-8 放小球

这道题，我们一定能通过一种方式将最终解构造出来

从后往前遍历

如果当前箱子的倍数箱子放小球数对2取余不满足这个属性，那就在这个箱子放，否则不放

代码：

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int N = 200010, M = N * 2, mod = 1e9 + 7;
int n, m;
int a[N],b[N];
vector<int> res;
int main() {cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];}for (int i = n; i >= 1; i--) {int sum = 0;for (int k = 2; i * k <= n; k++)sum += b[i * k];if (sum % 2 == 0) {if (a[i]) {res.push_back(i);b[i] = 1;}}else {if(!a[i]) {res.push_back(i);b[i] = 1;}}}cout << res.size() << endl;for (int i = 0; i < res.size(); i++) {cout << res[i] << " ";}
}

7-9 给树染色

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int N = 100010, M = N * 2, mod = 1e9 + 7;
int n, m;
int tol[N];
int h[N], e[M], ne[M], idx;
LL sum = 1;
void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs1(int cur, int fa) {int x;if (cur == 1)x = m - 1;else x = m - 2;for (int i = h[cur]; i != -1; i = ne[i]) {int j = e[i];if (j == fa)continue;tol[j] = x--;dfs1(j, cur);}
}
void dfs2(int u, int fa) {sum = (sum * tol[u]) % mod;for (int i = h[u]; i != -1; i = ne[i]) {int j = e[i];if (j == fa)continue;dfs2(j, u);}
}int main() {cin >> n >> m;memset(h, -1, sizeof h);for (int i = 1; i < n; i++) {int a, b;cin >> a >> b;add(a, b), add(b, a);}tol[1] = m;dfs1(1, 0);dfs2(1, 0);cout << sum;}

7-10 摆放小球

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2010, mod = 1e9 + 7;
int n, a, b, x;
int fact[N], infact[N];
int qmi(int a, int k, int p) {int res = 1;while (k) {if (k & 1)res = (LL)res * a % p;k >>= 1;a = (LL)a * a % p;}return res;
}
int C(int a, int b) {return (LL)fact[a] * infact[b] % mod * infact[a - b] % mod;
}int main() {fact[0] = infact[0] = 1;for (int i = 1; i < N; i++) {fact[i] = (LL)fact[i - 1] * i % mod;infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;}scanf("%d%d", &n, &x);for (int i = 1; i <= x; i++) {if (i > n - x + 1)cout << 0 << endl;else cout << (LL)C(n - x + 1, i) * C(x - 1,i - 1) % mod <<endl;}return 0;
}

7-11 区间的个数

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int N = 1e5+10, M = 1e6+10, mod = 1e9 + 7;
int n;
LL m;
LL a[N];
int main()
{cin >> n >> m;for (int i = 0; i < n; i++)cin >> a[i];int l = 0, r = 0;LL res = 0;LL sum = 0;while (r < n) {while(sum < m && r < n) {sum += a[r];r++;}if (sum >= m)res += n - r + 1;sum -= a[l++];while (sum >= m) {sum -= a[l++];res += n - r + 1;}}cout << res;return 0;
}

7-12 选零食

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 55;int n, m;
int a[N];
int res;
int main() {cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> a[i];}int buy = min(n, m);for (int i = 1; i <= buy; i++) {int put = m - i;for (int jl = 0; jl <= i; jl++) {int sum = 0;priority_queue<int, vector<int>, greater<int>> q;int jr = n - i + jl + 1;for (int j = 1; j <= jl; j++) {q.push(a[j]);sum += a[j];}for (int j = jr; j <= n; j++) {q.push(a[j]);sum += a[j];}int x = put;while (!q.empty() && q.top() < 0 && x > 0) {sum -= q.top();q.pop();x--;}res = max(res, sum);}}cout << res;return 0;
}

7-13 小球之间的距离

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10, mod = 1e9 + 7;
int n, m, k;int qmi(int a, int k, int p)
{int res = 1;while (k){if (k & 1) res = (LL)res * a % p;a = (LL)a * a % p;k >>= 1;}return res;
}int C(int a, int b, int p)
{if (b > a) return 0;int res = 1;for (int i = 1, j = a; i <= b; i++, j--){res = (LL)res * j % p;res = (LL)res * qmi(i, p - 2, p) % p;}return res;
}int main() {cin >> n >> m >> k;int tmp = (LL)m * m % mod;LL sum = 0,sum2 = 0;for (int i = 1; i < n; i++) {sum = (sum + (LL)i * (n - i) % mod) % mod;}sum = sum * tmp % mod;tmp = (LL)n * n % mod;for (int i = 1; i < m; i++) {sum2 = (sum2 + (LL)i * (m - i) % mod) % mod;}sum2 = sum2 * tmp % mod;sum = ((sum + sum2) % mod * C(n * m - 2, k - 2, mod)) % mod;cout << sum;return 0;
}

7-14 1还是2

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int N = 1e5+10, M = 1e6+10, mod = 1e9 + 7;
int n, m;
int p[N];int find(int x) {if (x != p[x])p[x] = find(p[x]);return p[x];
}int main()
{cin >> n >> m;for (int i = 1; i <= n; i++)p[i] = i;for (int i = 0; i < m; i++) {int a, b, c;cin >> a >> b >> c;a = find(a), b = find(b);if (a != b)p[a] = b;}set<int> st;for (int i = 1; i <= n; i++) {p[i] = find(p[i]);st.insert(p[i]);}cout << st.size();return 0;
}

7-15 青春猪头之我没学过C语言

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int N = 1e5+10, M = 1e6+10, mod = 1e9 + 7;
int n;
LL x, y;
LL fun(LL x) {if (x % 4 == 1)return 1;else if (x % 4 == 2)return x + 1;else if (x % 4 == 3)return 0;else return x;
}
int main()
{cin >> x >> y;LL res = fun(max((LL)0,x - 1)) ^ fun(y);cout << res;return 0;
}

7-16 打怪兽

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;
#define clr(a,b) memset(a,b,sizeof(a))
const int maxn=700+2;
const int inf=0x3f3f3f3f;
typedef long long ll;
struct Node
{int maxw,cnt;Node(){}Node(int maxw,int cnt):maxw(maxw),cnt(cnt){}bool operator > (Node t){return maxw>t.maxw;}
}tree[maxn<<2][maxn<<2];
int m,n,q,r,mat[maxn][maxn];
Node ans;
void push_upy(int deep,int k)
{tree[deep][k].maxw=max(tree[deep][k<<1].maxw,tree[deep][k<<1|1].maxw);if(tree[deep][k].maxw==tree[deep][k<<1].maxw)tree[deep][k].cnt+=tree[deep][k<<1].cnt;if(tree[deep][k].maxw==tree[deep][k<<1|1].maxw)tree[deep][k].cnt+=tree[deep][k<<1|1].cnt;return ;
}
void push_upx(int deep,int k)
{tree[deep][k].maxw=max(tree[deep<<1][k].maxw,tree[deep<<1|1][k].maxw);if(tree[deep][k].maxw==tree[deep<<1][k].maxw)tree[deep][k].cnt+=tree[deep<<1][k].cnt;if(tree[deep][k].maxw==tree[deep<<1|1][k].maxw)tree[deep][k].cnt+=tree[deep<<1|1][k].cnt;return ;
}
void bulid_y(int ly,int ry,int deep,int k,int flag)
{tree[deep][k].maxw=-inf;if(ly==ry){if(flag){scanf("%d",&tree[deep][k].maxw);mat[r][ly]=tree[deep][k].maxw;tree[deep][k].cnt=1;}else {push_upx(deep,k);}//更新x方向return ;}int mind=(ly+ry)>>1;//bulid_y(ly,mind,deep,k<<1,flag);bulid_y(ly,mind,deep,k<<1,flag);bulid_y(mind+1,ry,deep,k<<1|1,flag);push_upy(deep,k);return ;
}
void bulid_x(int lx,int rx,int deep)
{if(lx==rx){r=lx;bulid_y(1,n,deep,1,1);return ;}int mind=(lx+rx)>>1;bulid_x(lx,mind,deep<<1);bulid_x(mind+1,rx,deep<<1|1);bulid_y(1,n,deep,1,0);//同区域y轴方向return ;
}
void query_y(int ly,int ry,int Ly,int Ry,int deep,int k)
{if(Ly<=ly&&ry<=Ry){if(ans.maxw==tree[deep][k].maxw){ans.cnt+=tree[deep][k].cnt;}else if(tree[deep][k]>ans){ans=tree[deep][k];}return;}int mind=(ly+ry)>>1;if(Ly<=mind)query_y(ly,mind,Ly,Ry,deep,k<<1);if(Ry>mind)query_y(mind+1,ry,Ly,Ry,deep,k<<1|1);return ;
}
void query_x(int lx,int rx,int Lx,int Rx,int Ly,int Ry,int deep)
{if(Lx<=lx&&rx<=Rx){query_y(1,n,Ly,Ry,deep,1);return;}int mind=(lx+rx)>>1;if(Lx<=mind)query_x(lx,mind,Lx,Rx,Ly,Ry,deep<<1);if(Rx>mind)query_x(mind+1,rx,Lx,Rx,Ly,Ry,deep<<1|1);return ;
}
int main()
{int t;cin >> t;while(t--){scanf("%d%d",&m,&n);clr(tree,0);clr(mat,0);bulid_x(1,m,1);scanf("%d",&q);int x1,y1,x2,y2;while(q--){scanf("%d%d%d%d",&x1,&y1,&x2,&y2);ans.maxw=0;ans.cnt=0;query_x(1,m,x1,x2,y1,y2,1);printf("%d\\n",ans.maxw);}}return 0;
}

7-17 背上书包去旅行

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 20,M = 1 << N, mod = 1e9 + 7;
int n, m;
int w[N][N];
int f[M][N];
struct NODE {int a, b, c;
}node[N];int main()
{cin >> n;int i = 0;for (; i < n; i++)cin >> node[i].a >> node[i].b >> node[i].c;node[i].a = node[0].a, node[i].b = node[0].b, node[i].c = node[0].c;n++;for (i = 0; i < n; i++) {for (int j = 0; j < n; j++) {w[i][j] = abs(node[j].a - node[i].a) + abs(node[j].b - node[i].b) + max(0, node[j].c - node[i].c);}}memset(f, 0x3f, sizeof(f));f[1][0] = 0;for (i = 1; i < (1 << n); i++) {for (int j = 0; j < n; j++) {if (i >> j & 1) {for (int k = 0; k < n; k++) {if (i >> k & 1) {f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);}}}}}cout << f[(1 << n) - 1][n - 1];return 0;
}

7-18 向前走

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 200010;
int n,w;
LL s[N],t[N];int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%lld",&s[i]);s[i]+=s[i-1];t[i] = max(s[i],t[i-1]);//cout<<t[i]<<endl;}LL res=0;for(int i=1;i<=n;i++){res=max(res,s[i-1]+t[i]);s[i]+=s[i-1];}cout<<res;return 0;
}

7-19 热水器

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 200010;
LL n,w;
LL s[N];int main()
{scanf("%lld%lld",&n,&w);int l,r,c,maxn=0;for(int i=0;i<n;i++){scanf("%d%d%d",&l,&r,&c);s[l]+=c,s[r]-=c;maxn=max(maxn,r+1);}bool fg = true;for(int i=0;i<=maxn+1;i++){if(i!=0)s[i]+=s[i-1];if(s[i]>w){fg=false;break;}}if(fg)printf("Yes");else printf("No");return 0;
}

7-20 走方格

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2010, mod = 1e9 + 7;
int n, m;
char ch[N][N];
LL f[N][N];
LL s1[N][N],s2[N][N],s3[N][N];int main()
{scanf("%d%d", &n, &m);getchar();for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++)scanf("%c", &ch[i][j]);getchar();}f[1][1] = 1,s1[1][1]= s2[1][1] = s3[1][1] =1;for(int i=1;i<=n;i++)for (int j = 1; j <= m; j++) {if (ch[i][j] == '#') { continue; }f[i][j] += ((s1[i - 1][j] + s2[i][j - 1])%mod + s3[i - 1][j - 1])%mod;s1[i][j] = (f[i][j] + s1[i - 1][j])%mod;s2[i][j] = (f[i][j] + s2[i][j - 1]) % mod;s3[i][j] = (f[i][j] + s3[i - 1][j - 1]) % mod;}/*for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cout << f[i][j]<<" ";}cout << endl;}*/cout << f[n][m];return 0;
}

7-21 朋友圈

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 200010, mod = 1e9 + 7;
int n, q, x;
int a, b, c;
int p[N];
map<int, int> res[N];
int siz[N];
int find(int x) {if (x != p[x])p[x] = find(p[x]);return p[x];
}int main()
{cin >> n >> q;for (int i = 1; i <= n; i++) {siz[i] = 1;scanf("%d", &x);res[i][x]++;p[i] = i;}while (q--) {scanf("%d%d%d" ,&c, &a, &b);if (c == 1) {a = find(a), b = find(b);if (a != b) {if (siz[a] > siz[b]) {p[b] = a;siz[a] += siz[b];for (auto it : res[b]) {res[a][it.first] += it.second;}}else {p[a] = b;siz[b] += siz[a];for (auto it : res[a]) {res[b][it.first] += it.second;}}}}else {a = find(a);printf("%d\\n", res[a][b]);}}return 0;
}

7-22 走方格

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 200010, mod = 1e9 + 7;
int n, m, a, b;int fact[N], infact[N];
int qmi(int a, int k, int p)
{int res = 1;while (k){if (k & 1) res = (LL)res * a % p;a = (LL)a * a % p;k >>= 1;}return res;
}LL com(int n, int m) {return ((LL)fact[n] * infact[m] % mod * infact[n - m]) % mod;
}int main()
{scanf("%d%d%d%d", &n, &m, &a, &b);fact[0] = infact[0] = 1;for (int i = 1; i < N; i++){fact[i] = (LL)fact[i - 1] * i % mod;infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;}LL res = 0;for (int i = 0; i < n - a; i++) {LL t = ((LL)com(b + i - 1, b - 1) * com(n + m - b - i - 2, n - i - 1))%mod;res = (res + t)%mod;}cout << res;return 0;
}

7-23 和与积

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL S, P;
int main()
{cin >> S >> P;LL j = 0;for (LL i = 1; i <= P/i; i++) {j = S - i;if ((LL)i * j == P) {cout << "Yes";return 0;}}cout << "No";return 0;
}

7-24 增加硬币

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 110;
double f[N][N][N];
int d = 0;double dp(int a, int b, int c) {if (f[a][b][c] >= 0)return f[a][b][c];f[a][b][c] = 0;if (a >= 100 || b >= 100 || c >= 100)return f[a][b][c];int sum = a + b + c;f[a][b][c] += (dp(a + 1, b, c) + 1) * (1.0 * a) / sum;f[a][b][c] += (dp(a, b + 1, c) + 1) * (1.0 * b) / sum;f[a][b][c] += (dp(a, b, c + 1) + 1) * (1.0 * c) / sum;return f[a][b][c];
}
int main()
{int a, b, c;scanf("%d%d%d", &a, &b, &c);memset(f, -1, sizeof f);printf("%.9lf", dp(a, b, c));return 0;
}

7-25 日落大道

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 2010;
int n, m;
char ch;
char s[N][N];
int d[N][N];vector<PII> mp[30];
int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };int main()
{scanf("%d%d", &n, &m);getchar();int x, y, resx, resy;memset(d, 0x3f, sizeof d);for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {scanf("%c", &ch);s[i][j] = ch;if (ch >= 'a' && ch <= 'z')mp[ch - 'a'].push_back({i,j});else if (ch == 'S')x = i, y = j;else if (ch == 'G')resx = i, resy = j;}getchar();}queue<PII> q;q.push({ x,y });d[x][y] = 0;while (q.size()) {PII t = q.front();q.pop();for (int i = 0; i < 4; i++) {int a = t.first + dx[i], b = t.second + dy[i];if (a<1 || a>n || b<1 || b>m || s[a][b] == '#')continue;if (d[a][b] > d[t.first][t.second] + 1) {d[a][b] = d[t.first][t.second] + 1;q.push({ a,b });}if (s[a][b] == 'G')break;if (s[a][b] >= 'a' && s[a][b] <= 'z') {for (auto it : mp[s[a][b] - 'a']) {if (it.first == a && it.second == b)continue;if (d[it.first][it.second] > d[a][b] + 1) {d[it.first][it.second] = d[a][b] + 1;q.push({ it.first,it.second });}mp[s[a][b] - 'a'].clear();}}}}if (d[resx][resy] == 0x3f3f3f3f)printf("-1");else printf("%d", d[resx][resy]);return 0;
}

7-26 ICPC保定站

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 50;
typedef pair<int, int> PII;
int n, t, k;
int w[N];
LL weights[1 << 24], cnt = 0;
LL res;void dfs1(int u, LL s) {if (u == k) {weights[cnt++] = s;return;}dfs1(u + 1, s);if (s + w[u] <= t)dfs1(u + 1, s + w[u]);
}void dfs2(int u, LL s) {if (u == n) {int l = 0, r = cnt - 1;while (l < r) {int mid = l + r + 1 >> 1;if (weights[mid] <= (LL)t - s)l = mid;else r = mid - 1;}if (weights[l] + s <= t)res = max(res, weights[l] + s);return;}dfs2(u + 1, s);if (w[u] + s <= t)dfs2(u + 1, s + w[u]);
}int main()
{scanf("%d%d", &n, &t);for (int i = 0; i < n; i++)scanf("%d", &w[i]);sort(w, w + n);reverse(w, w + n);k = n / 2;dfs1(0, 0);sort(weights, weights + cnt);cnt = unique(weights, weights + cnt) - weights;dfs2(k, 0);cout << res;return 0;
}

7-27 简单的异或

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 300010;int n, m;
int a[N], tr[N];int lowbit(int x)
{return x & -x;
}void add(int x, int v)
{for (int i = x; i <= n; i += lowbit(i)) tr[i] ^= v;
}int query(int x)
{int res = 0;for (int i = x; i; i -= lowbit(i)) res ^= tr[i];return res;
}int main()
{scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++) scanf("%d", &a[i]);for (int i = 1; i <= n; i++) add(i, a[i]);while (m--){int k, x, y;scanf("%d%d%d", &k, &x, &y);if (k == 2) printf("%d\\n", query(y) ^ query(x - 1));else add(x, y);}return 0;
}

7-28 选我啊！

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
struct stu {LL a, b, c;
}st[N];LL resa;
int n;
bool cmp(stu s1, stu s2) {return s1.c > s2.c;
}
int main()
{scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d%d", &st[i].a, &st[i].b);resa += st[i].a;st[i].c = st[i].a * 2 + st[i].b;}sort(st, st + n, cmp);int res = 0;for (int i = 0; i < n; i++) {if (resa < 0)break;resa -= st[i].c;res++;}cout << res;return 0;
}

7-29 豪华酒店

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 4e5+10;
int n,m;
int a,b,c;
struct node{int x;int money;
}s[N];
int cnt;
LL sum = 0;
LL res=0,pre = 0;
bool cmp(node n1,node n2){if(n1.x==n2.x)return n1.money>n2.money;return n1.x<n2.x;
}
int main()
{scanf("%d%d",&n,&m);for(int i=0;i<n;i++){scanf("%d%d%d",&a,&b,&c);s[cnt].x=a,s[cnt++].money=c;s[cnt].x=b+1,s[cnt++].money=-c;}sort(s,s+cnt,cmp);for(int i=0;i<cnt;i++){if(!i){pre = s[i].money;}else{int d = s[i].x-s[i-1].x;sum+=(LL)d*res;pre += s[i].money;}res = min(pre,(LL)m);}cout<<sum;return 0;
}

7-30 摆放小球

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 105;
int n, m, a, b, k;
int st[N];
pair<int, int> f[N], s[N];
int sum = 0;
void dfs(int u) {if (u == k + 1) {int res = 0;for (int i = 1; i <= m; i++) {if (st[f[i].first]!=0 && st[f[i].second] != 0)res++;}sum = max(sum, res);return;}st[s[u].first]++;dfs(u + 1);st[s[u].first]--;st[s[u].second]++;dfs(u + 1);st[s[u].second]--;
}int main()
{memset(st, 0, sizeof st);scanf("%d%d", &n, &m);for (int i = 1; i <= m; i++) {scanf("%d%d", &a, &b);f[i].first = a, f[i].second = b;}scanf("%d", &k);for (int i = 1; i <= k; i++) {scanf("%d%d", &a, &b);s[i].first = a, s[i].second = b;}dfs(1);cout << sum;//if(a[n]==0)cout<<"Yes";//else cout<<"No";return 0;
}

7-31 最大公约数的和

#include<cstdio>
#define re register int
long long n, ans, f[4000010];
int main() {scanf("%lld", &n);for (re i = n; i; --i) {f[i] = n / i * (n / i);for (int j = i << 1; j <= n; j += i)f[i] -= f[j];ans += (f[i] * i - i)/2;}printf("%lld", ans);return 0;
}

7-32 一道简单题

#include <bits/stdc++.h>using namespace std;
int n;int main()
{cin >> n;map<int, int> mp;for (int i = 0; i <= 30; i++) {for (int j = 0; j <= 30; j++) {if (i == j)continue;int x = (1 << i) + (1 << j);mp[x] = 1;}}int minn = 1e9 + 10;for (auto it : mp) {minn = min(minn, abs(it.first - n));}cout << minn;return 0;
}

7-33 一个无限大的集合

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10, mod = 998244353;
typedef long long LL;
int f[N];
int p;int main() {f[1] = 1;LL res = 1;cin >> p;for (int i = 2; i <= p; i++) {f[i] = (f[i - 1] + f[i - 2]) % mod;res = (res + f[i]) % mod;}cout << res;
}