题解"/>
CSP部分题题解
CSP
202203
1 田地丈量
题意：
给定 n n n 块互不相交的矩形，询问 ( 0 , 0 ) ( a , b ) (0,0)(a, b) (0,0)(a,b) 区域内矩形面积和
解析：
先判断矩形跟区域是否有重叠的部分，如果有，求出重叠的部分
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int maxn = 1e5+10;
const int INF = 0x3f3f3f3f;
#define fi first
#define se second
typedef pair<int, int> pii;ll n, a, b;
ll ans;ll cal(ll x1, ll y1, ll x2, ll y2){x1 = max(x1, 0ll);y1 = max(y1, 0ll);x2 = min(x2, a);y2 = min(y2, b);ll res = (x2 - x1) * (y2 - y1);return res;
}
int main(){ ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n >> a >> b;for(int i = 1; i <= n; i++){ll x1, x2, y1, y2;cin >> x1 >> y1 >> x2 >> y2;if(x2 <= 0 || y2 <= 0 || x1 >= a || y1 >= b)continue; ans += cal(x1, y1, x2, y2);}cout << ans;return 0;
}
2 垦田计划
题意：
n n n 块土地，每块土地花费 t i t_i ti天，总耗时为最大的时间。有 m m m 资源，在第 i i i 块土地使用 c i c_i ci 资源可以使时间减少一天。询问最少需要多少天
解析：
使最大的 t i t_i ti 最小，可以二分答案。对于当前的时间 x x x ，如果一块土地的时间大于 x x x，则花费资源将时间减少到 x x x花费的资源是否小于 m m m
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int maxn = 1e5+10;
const int INF = 0x3f3f3f3f;
#define fi first
#define se second
typedef pair<int, int> pii;int n, m, k;
int t[maxn], c[maxn];
int ans;
bool check(int x){int cost = 0;for(int i = 1; i <= n; i++){if(t[i] > x){cost += c[i] * (t[i]-x);}}return cost <= m;
}
int main(){ ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n >> m >> k;int l = k, r = 0;for(int i = 1; i <= n; i++){cin >> t[i] >> c[i];r = max(r, t[i]);}while(l <= r){int mid = (l+r) >>1;if(check(mid)){r = mid-1; ans = mid;}elsel = mid+1;}cout << ans;return 0;
}3 LDAP
题意
每个用户有若干属性，每个属性有一个值。
有 m m m 个表达式，选出满足表达式的用户。
40分解析：
直接模拟即可
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int maxn = 1e5+10;
const int maxm = 505;#define fi first
#define se second
typedef pair<int, int> pii;struct User{int id;vector<int> s;User(){s.resize(505);for(int i = 0; i < s.size(); i++)s[i] = -1;}
};
struct Base{int op; // 1 为满足 2为不满足 int pos, val;
};
struct Expr{int op; //0 为原子，1为&，2为| Base expr1;Base expr2;
};vector<User> users;
vector<Expr> exprs;
int n, m;
Base exchangeBase(string s){int pos = 0;for(int i = 0; i < s.size(); i++){if(s[i] == ':' || s[i] == '~'){pos = i;break;}}Base base;int x = 0, val = 0;for(int i = 0; i < pos; i++)x = x * 10 + s[i]-'0';for(int i = pos+1; i < s.size(); i++)val = val * 10 + s[i] -'0';if(s[pos] == ':')base.op = 1;else base.op = 2;base.pos = x;base.val = val; return base;
}
void check(Expr expr){vector<int> res;res.clear();for(int i = 0; i < users.size(); i++){User user = users[i];if(expr.op == 0){if(expr.expr1.op == 1){ // 相等 if(user.s[expr.expr1.pos] == expr.expr1.val)res.push_back(user.id);}else if(expr.expr1.op == 2){if(user.s[expr.expr1.pos] != -1)if(user.s[expr.expr1.pos] != expr.expr1.val)res.push_back(user.id);}}else if(expr.op == 1){ // 且int flag1 = 0, flag2 = 0; if(expr.expr1.op == 1){ // 相等 if(user.s[expr.expr1.pos] == expr.expr1.val)flag1 = 1;}else if(expr.expr1.op == 2){if(user.s[expr.expr1.pos] != -1)if(user.s[expr.expr1.pos] != expr.expr1.val)flag1 = 1;}if(flag1 == 0)continue;if(expr.expr2.op == 1){ // 相等 if(user.s[expr.expr2.pos] == expr.expr2.val)flag2 = 1;}else if(expr.expr2.op == 2){if(user.s[expr.expr2.pos] != -1)if(user.s[expr.expr2.pos] != expr.expr2.val)flag2 = 2;}if(flag1 && flag2)res.push_back(user.id);}else{int flag1 = 0, flag2 = 0; if(expr.expr1.op == 1){ // 相等 if(user.s[expr.expr1.pos] == expr.expr1.val)flag1 = 1;}else{if(user.s[expr.expr1.pos] != -1)if(user.s[expr.expr1.pos] != expr.expr1.val)flag1 = 1;}if(flag1){res.push_back(user.id);continue;}if(expr.expr2.op == 1){ // 相等 if(user.s[expr.expr2.pos] == expr.expr2.val)flag2 = 1;}else if(expr.expr2.op == 2){if(user.s[expr.expr2.pos] != -1)if(user.s[expr.expr2.pos] != expr.expr2.val)flag2 = 2;}if(flag2)res.push_back(user.id);}}sort(res.begin(), res.end());for(int i = 0; i < res.size(); i++){if(i != 0)cout << " " << res[i];elsecout << res[i];}cout << endl;
}
int main(){ ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n;for(int i = 1; i <= n; i++){User user;int id, cnt;cin >> id >> cnt;for(int j = 1; j <= cnt; j++){int x, val;cin >> x >> val;user.s[x] = val;}user.id = id;users.push_back(user);}cin >> m;for(int k = 1; k <= m; k++){string s;cin >> s;Expr expr;if(s[0] == '&' || s[0] == '|'){int len = 0;int pos = 0;for(int i = 1; i < s.size(); i++){if(s[i] == ')'){len = i - 2;pos = i;break;} }int len2 = s.size()-len-5;expr.expr1 = exchangeBase(s.substr(2, len));expr.expr2 = exchangeBase(s.substr(pos+2, len2));if(s[0] == '&')expr.op = 1;elseexpr.op = 2;}else{expr.expr1= exchangeBase(s);expr.op = 0;}exprs.push_back(expr);} for(int i = 0; i < exprs.size(); i++){check(exprs[i]);}return 0;
}5 施肥
题意：
有区间 [ 1 , n ] [1,n] [1,n]，有 m m m 辆车，每辆车可以恰好覆盖 [ l i , r i ] [l_i,r_i] [li,ri]。询问有多少二元组 ( L , R ) (L,R) (L,R) 满足 [ L , R ] [L,R] [L,R] 内的点都被覆盖至少一次， [ L , R ] [L,R] [L,R] 之外的点都没有被覆盖
75分解析：
复杂度为 O ( n 2 ) O(n^2) O(n2) 的思路：
容易发现，只有车的端点才有可能对答案产生贡献。
将所有车按右端点升序排序。
对于遍历到的当前车 i i i，统计 L = l i L = l_i L=li 的答案个数。
对于前边的车 k ( k < i ) k(k < i) k(k<i)， k k k 一定不会产生贡献，因为 r k ≤ r i r_k \le r_i rk≤ri。对于后边的车 j ( j > i ) j(j>i) j(j>i)，如果 l j < l i l_j < l_i lj<li ，则 j j j 不会对答案产生贡献；如果 l j > c u r R + 1 l_j > curR+1 lj>curR+1， j j j 区间连不上当前区间，也不会答案产生贡献。即 l j ≥ l i l_j \ge l_i lj≥li 且 l j < = c u r R + 1 l_j <= curR+1 lj<=curR+1 的 j j j 才会产生贡献，并用 r j r_j rj 更新 c u r R curR curR。( c u r R curR curR 为左端点为 l i l_i li 时，能连成的区间右端点最大值)
用 s e t set set 去掉重复的区间
对于特殊性质 A :区间不会包含
则任意两区间只能是 “相交”，“相离” 的关系。
依然按照右端点排序，预处理每个区间后能连上区间个数 g ( i ) g(i) g(i)。
倒序处理。如果区间 i i i 与区间 i + 1 i+1 i+1 相交，则 g ( i ) = g ( i + 1 ) + 1 g(i) = g(i+1)+1 g(i)=g(i+1)+1; 否则 g ( i ) = 0 g(i) = 0 g(i)=0
答案为 ∑ i ( 1 + g ( i ) ) \sum\limits_i(1+g(i)) i∑(1+g(i))，时间复杂度为 O ( n log n ) O(n\log n) O(nlogn)
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int maxn = 2e5+10;
const int INF = 0x3f3f3f3f;
#define fi first
#define se second
typedef pair<int, int> pii;struct node{int l, r;node(){}node(int l, int r) : l(l), r(r){}bool operator < (const node &b) const{if(r == b.r)return l < b.l;elsereturn r < b.r;}bool operator == (const node &b) const{return l == b.l && r == b.r;}
};
set<node> se;
int n, m;
//node s[maxn];
vector<node> s;
int g[maxn];
ll ans = 0;
int main(){ ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n >> m;for(int i = 1; i <= m; i++){//cin >> s[i].l >> s[i].r;int l, r;cin >> l >>r;s.push_back((node){l, r});}//sort(s+1, s+1+m);sort(s.begin(), s.end());//s.erase(unique(s.begin(), s.end()), s.end());if(n > 3000){g[m-1] = 0;for(int i = s.size()-2; i >= 0; i--){if(s[i].r >= s[i+1].l-1)g[i] = g[i+1]+1;elseg[i] = 0;}for(int i = 0; i < m; i++){ans += g[i]+1;}cout << ans << endl;return 0;}for(int i = 0; i < s.size(); i++){int curr = s[i].r;int res = 1;if(se.count(node(s[i].l, s[i].r)) == 0)se.insert(node(s[i].l, s[i].r));elseres = 0; for(int j = i+1; j < s.size(); j++){if(s[j].l < s[i].l)continue;if(s[j].l <= curr+1){curr = max(curr, s[j].r);if(se.count(node(s[i].l, s[j].r)) == 0){se.insert(node(s[i].l, s[j].r));res++;} }}ans += res;}cout << ans << endl;return 0;
}202212
1 现值计算
题目：
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 1e5+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;int n;
db x, res;
int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n >> x;for(int i = 0; i <= n; i++){db y; cin >> y;res += y * pow(1 + x, -i);}cout << setprecision(10) << res << endl;return 0;
}2 训练计划
题意：
一个科目耗时 t i t_i ti，一些科目有前置科目，只有当前置科目学完时，才能开始学当前科目。前置科目的编号一定小于当前科目。
询问每一项科目的最早开始时间。询问在完成的情况下的最晚开始时间，如果不能完成则不输出。
解析：
建图，科目看成节点，依赖关系看成边，前置科目向当前科目连边；对于没有前置科目的科目，0号节点向该节点连边。
在dfs的过程中，当前节点为 u u u，记录 u u u 的深度 d e p u dep_u depu，以及以 u u u 为根的子树的高度 m a x d e p u maxdep_u maxdepu，即 u u u 到 u u u 子树中节点的最大距离。
对节点 u u u ，执行完 u u u 的父亲之后就可以执行 u u u 。因此执行完 u u u 的父亲需要时间 d e p ( f a [ u ] ) dep(fa[u]) dep(fa[u])。从时刻 1 开始执行，所以 u u u 可以开始执行的时间为 1 + d e p ( f a [ u ] ) 1 + dep(fa[u]) 1+dep(fa[u])。
首先判断能不能全部执行完，即 m a x d e p 0 maxdep_0 maxdep0 是否大于 n n n。
然后对每个节点 u u u，执行完 u u u 子树的时间为 t u + m a x d e p u t_u + maxdep_u tu+maxdepu，所以答案为 n + 1 − t u − m a x d e p u n+1-t_u - maxdep_u n+1−tu−maxdepu
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 1e5+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;int n, m;
int p[maxn];
int t[maxn];
int head[maxn], tot;
struct edge{int to, nxt, w;
}e[maxn];
void add(int a, int b, int c){e[++tot].nxt = head[a];e[tot].to = b;e[tot].w = c;head[a] = tot;
}
int dep[maxn], maxdep[maxn], fa[maxn];
void dfs(int u){for(int i = head[u]; i; i = e[i].nxt){int v = e[i].to;int w = e[i].w;fa[v] = u;dep[v] = dep[u] + w;dfs(v);maxdep[u] = max(maxdep[u], w + maxdep[v]);}
}
int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n >> m;for(int i = 1; i <= m; i++)cin >> p[i];for(int i = 1; i <= m; i++)cin >> t[i];for(int i = 1; i <= m; i++){add(p[i], i, t[i]);}dfs(0); for(int i = 1; i <= m; i++)cout << 1 + dep[fa[i]]<< " ";cout << endl;if(maxdep[0] > n)return 0;for(int i = 1; i <= m; i++){int res = n - maxdep[i] - t[i] + 1;cout << res << " ";}return 0;}3 JPEG 解码
题意：
大模拟
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 1e5+10;
const int INF = 0x3f3f3f3f;
const db pi = acos(-1);
typedef pair<int, int> pii;int q[10][10];
db m[10][10];
db mres[10][10];
int ans[10][10];
int a[100];db f(int x){if(x == 0)return sqrt(0.5);elsereturn 1;
}int dx[6] = {0, 0, -1, 1, 1, -1};
int dy[6] = {-1, 1, 0, 0, -1, 1};int nxt[8][8] = {
{1, 4, 1, 4, 1, 4, 1, 4},
{3, 5, 4, 5, 4, 5, 4, 3},
{5, 4, 5, 4, 5, 4, 5, 4},
{3, 5, 4, 5, 4, 5, 4, 3},
{5, 4, 5, 4, 5, 4, 5, 4},
{3, 5, 4, 5, 4, 5, 4, 3},
{5, 4, 5, 4, 5, 4, 5, 4},
{1, 5, 1, 5, 1, 5, 1, -1}} ;// l r u d ld, ru 左0 右1 上2 下3 左下4 右上5void fillm(){int x = 0, y = 0;for(int i = 1; i <= 64; i++){ m[x][y] = a[i];int op = nxt[x][y];if(op == -1)break;x = x+dx[op];y = y+dy[op];}
}
void m_mul_q(){for(int i = 0; i < 8; i++)for(int j = 0; j < 8; j++)m[i][j] *= q[i][j];
}
void printm(){for(int i = 0; i < 8; i++){for(int j = 0; j < 8; j++)cout << m[i][j] << " ";cout << endl;}
}
db exchange(int i, int j){db res = 0;for(int u = 0; u < 8; u++)for(int v = 0; v < 8; v++)res += 0.25*f(u) * f(v) * m[u][v] * cos(pi/8*(i+0.5)*u) * cos(pi/8*(j+0.5)*v);//res /= 4;return res;
}
void change(){for(int i = 0; i < 8; i++)for(int j = 0; j < 8; j++)mres[i][j] = exchange(i, j);
}
void addm(){for(int i = 0; i < 8; i++){for(int j = 0; j < 8; j++){db res = mres[i][j] + 128;if(res > 255)ans[i][j] = 255;else if(res < 0)ans[i][j] = 0;else ans[i][j] = (int)(res+0.5);}}
}
void printans(){for(int i = 0; i < 8; i++){for(int j = 0; j < 8; j++)cout << ans[i][j] << " ";cout << endl;}
}
int n, T;
int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);for(int i = 0; i < 8; i++)for(int j = 0; j < 8; j++)cin >> q[i][j];cin >> n >> T;for(int i = 1; i <= n; i++)cin >> a[i];if(T == 0){fillm(); //3printm();} else if(T == 1){fillm(); //3m_mul_q(); //4printm();} else{fillm(); //3m_mul_q(); //4change();//5addm();//6printans();}return 0;
}4 聚集方差
题意：
给定一个树，询问每个子树 u u u 的 g ( A u ) = ∑ i min j ≠ i ( a i − a j ) 2 g(A_u) = \sum\limits_i \min\limits_{j \neq i}(a_i-a_j)^2 g(Au)=i∑j=imin(ai−aj)2。 A u A_u Au 是 u u u 子树的节点集， i , j i,j i,j 是节点集中的节点， a a a 是节点的点权。
解析：
65分解析：
对于一个集合 A u A_u Au，差的最小绝对值一定是排序后的相邻位置，所以先排序，然后计算 g ( A u ) g(A_u) g(Au)，计算一次的时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)。
dfs的时候，合并儿子的子树，然后计算当前节点的 g ( A u ) g(A_u) g(Au)。总的时间复杂度为 O ( n 2 l o g n ) O(n^2logn) O(n2logn)
100解析：树上启发式合并（DSU ON TREE）暂时还不会
65分代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 3e5+10;
const ll INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int, int> pii;int n;
ll fans[maxn];
ll a[maxn];
struct edge{int to, nxt;
}e[maxn << 1];
int head[maxn], tot;
void add(int a, int b){e[++tot].nxt = head[a];e[tot].to = b;head[a] = tot;
}
vector<ll> merge(vector<ll> &src1,vector<ll> &src2){vector<ll> res;int i = 0, j = 0;for(; i < src1.size()&& j < src2.size(); ){if(src1[i] < src2[j]) res.push_back(src1[i++]);else res.push_back(src2[j++]);}while(i < src1.size()) res.push_back(src1[i++]);while(j < src2.size()) res.push_back(src2[j++]);return res;
}ll cal(vector<ll> s){if(s.size() == 1)return 0;sort(s.begin(), s.end());ll answ = 0;for(int i = 0; i < s.size(); i++){ll res = INF;if(i > 0)res = min(res, (s[i]-s[i-1]) * (s[i]-s[i-1]));if(i + 1 < s.size())res = min(res, (s[i]-s[i+1]) * (s[i]-s[i+1]));answ += res;}return answ;
}
vector<ll> dfs(int u){vector<ll> res;res.push_back(a[u]);vector<ll> s;for(int i = head[u]; i; i = e[i].nxt){int v = e[i].to;s = dfs(v);res = merge(res, s);}fans[u] = cal(res);return res;
}int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n;for(int i = 2; i <= n; i++){int x; cin >> x;add(x, i);}for(int i = 1; i <= n; i++)cin >> a[i];dfs(1);for(int i = 1; i <= n; i++)cout << fans[i] << endl;return 0;
}202209
1 如此编码
题意：
给定序列 a a a， a a a 的前缀积为序列 c c c。给定 m m m， m = ∑ i = 1 n c i − 1 × b i m = \sum\limits_{i=1}\limits^nc_{i-1}\times b_i m=i=1∑nci−1×bi。求序列 b b b
解析：
通过取模得到 c i − 1 × b i c_{i-1}\times b_i ci−1×bi 的前缀和，然后得到每一个 c i − 1 × b i c_{i-1} \times b_i ci−1×bi，然后得到 b i b_i bi
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
#define endl '\n'
const int maxn = 1e5+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;int n, m;
int a[maxn], b[maxn], c[maxn];
void solve(){cin >> n >> m;for(int i = 1; i <= n; i++)cin >> a[i];c[0] = 1;for(int i = 1; i <= n; i++)c[i] = c[i-1] * a[i];for(int i = 1; i <= n; i++)b[i] = m % c[i];for(int i = n; i >= 2; i--)b[i] = b[i]-b[i-1]; for(int i = 1; i <= n; i++)b[i] = b[i]/c[i-1];for(int i = 1; i <= n; i++) cout << b[i] << " ";cout << endl;return;
}
int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);int T = 1;while(T--)solve();return 0;
}2 何以包邮？
题意:
选一些书，使价值和 m m m 满足 m ≥ x m \ge x m≥x 且最小
代码：
01背包。
令 f i , j f_{i,j} fi,j 为前 i i i 本书，价值和为 j j j 是否可行。
状态转移方程为 f i , j = f i − 1 , j ∣ f i − 1 , j − a i f_{i,j} = f_{i-1,j} | f_{i-1,j-a_i} fi,j=fi−1,j∣fi−1,j−ai
初值为 f 0 , 0 = 1 f_{0,0} = 1 f0,0=1
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 3e5+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;int f[maxn], a[maxn];int n, x, v;
void solve(){cin >> n >> x;f[0] = 1;for(int i = 1; i <= n; i++){cin >> a[i];v += a[i];}for(int i = 1; i <= n; i++){for(int j = v; j >= a[i]; j--){f[j] |= f[j-a[i]];}}for(int i = x; i <= v; i++){if(f[i]){cout << i << endl;return;}}return;
}
int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);int T = 1;while(T--)solve();return 0;
}3 防疫大数据
题意：
大模拟
解析：
用set维护当天风险地区，vector保存当前的记录。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 1e4+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;struct pmsg{int d, u, r;pmsg(int d, int u, int r) : d(d), u(u), r(r){}pmsg(){}};
vector<pmsg> pm[maxn];
set<int> rm[maxn];
vector<int> res[maxn];int n, r, m;
void solve(){cin >> n;for(int i = 0; i < n; i++){cin >> r >> m;for(int j = 1; j <= r; j++){int a;cin >> a;for(int k = i; k <= min(i+6, n); k++)rm[i].insert(a);}for(int j = 1; j <= m; j++){int a, b, c;cin >> a >> b >> c;pm[i].push_back(pmsg(a, b, c));}int st = max(i-6, 0);for(int j = st; j <= i; j++){for(int k = 0; k < pm[j].size(); k++){int u = pm[j][k].u;int d = pm[j][k].d;int r = pm[j][k].r;if(d < st)continue;int flag = 1; for(int kk = d; kk <= i; kk++){if(rm[kk].count(r) == 0){flag = 0;break;}}if(flag)res[i].push_back(u);}}}for(int i = 0; i < n; i++){cout << i << ": ";sort(res[i].begin(), res[i].end());res[i].erase(unique(res[i].begin(), res[i].end()), res[i].end());for(int j = 0; j < res[i].size(); j++)cout << res[i][j] << " ";cout << endl;}return;
}
int main(){ solve();return 0;
}
202206
1 归一化处理
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 1e5+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;db a[maxn], n;
db ave, d;
db f(db x){db res = (x-ave)/sqrt(d);return res;
}
void solve(){cin >> n;for(int i = 1; i <= n; i++){cin >> a[i];ave += a[i];}ave /= n;for(int i = 1; i <= n; i++)d += (a[i] - ave) * (a[i] - ave);d /= n; for(int i = 1; i <= n; i++)cout << setprecision(12) << f(a[i]) << endl; return;
}
int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);int T = 1;while(T--)solve();return 0;
}2 寻宝！大冒险！
解析：
对每棵树，维护以该树为左下角的附近的树的位置。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 1e3+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;int n, l, s;
int a[55][55];struct tree{int x, y;int c[55][55];tree(){memset(c, 0, sizeof(c));}tree(int x, int y) : x(x), y(y){c[0][0] = 1;}void add(int px, int py){if(px < x || px > x + s || py < y || py > y + s)return;int tx = px - x;int ty = py - y;c[tx][ty] = 1;}bool check(){if(x > l-s || y > l-s)return false;for(int i = 0; i <= s; i++){for(int j = 0; j <= s; j++){if(a[i][j] != c[i][j])return false;}}return true;}
}t[maxn];void solve(){cin >> n >> l >> s;for(int i = 1; i <= n; i++){int x, y;cin >> x >> y;t[i] = tree(x, y);}for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){if(i == j)continue;int tx = t[j].x;int ty = t[j].y;t[i].add(tx, ty);}}for(int i = s; i >= 0; i--){for(int j = 0; j <= s; j++){cin >> a[i][j];}}int ans = 0;for(int i = 1; i <= n; i++){if(t[i].check())ans++;}cout << ans << endl;return;}
int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);int T = 1;while(T--)solve();return 0;
}3 角色授权
题意：
大模拟
解析：
每个角色是三个集合，存该角色的信息。
用map存名字字符串到类的映射，从而根据名快速找到类。
注意常数级别的优化。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
#define endl '\n'
const int maxn = 1e5+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;
typedef set<string>::iterator S_IT;struct role{set<string> op;set<string> kind;set<string> source;
};
struct group{set<string> ro;
};
struct people{set<string> gr;set<string> ro;
};map<string, role> mprole;
map<string, group> mpgroup;
map<string, people> mppeople;bool check(people user, string opt, string kindt, string sourcet){for(S_IT it = user.ro.begin(); it != user.ro.end(); it++){string roname = *it;int flag1 = mprole[roname].op.count("*") || mprole[roname].op.count(opt);if(flag1 == 0) continue;int flag2 = mprole[roname].kind.count("*") || mprole[roname].kind.count(kindt); if(flag2 == 0) continue;int flag3 = mprole[roname].source.empty() || mprole[roname].source.count(sourcet);if(flag3 == 0) continue;return true;}for(S_IT it = user.gr.begin(); it != user.gr.end(); it++){string grname = *it; if(mpgroup.count(grname) == 0)continue;for(S_IT itt = mpgroup[grname].ro.begin(); itt != mpgroup[grname].ro.end(); itt++){string roname = *itt;int flag1 = mprole[roname].op.count("*") || mprole[roname].op.count(opt);if(flag1 == 0) continue;int flag2 = mprole[roname].kind.count("*") || mprole[roname].kind.count(kindt); if(flag2 == 0) continue;int flag3 = mprole[roname].source.empty() || mprole[roname].source.count(sourcet);if(flag3 == 0) continue;return true;}}return false;
}
int n, m, q;
int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n >> m >> q;string name, tmp;int nv, no, nn;for(int i = 1; i <= n; i++){ //角色role cin >> name >> nv;for(int j = 1; j <= nv; j++){cin >> tmp;mprole[name].op.insert(tmp);}cin >> no;for(int j = 1; j <= no; j++){cin >> tmp;mprole[name].kind.insert(tmp);}cin >> nn;for(int j = 1; j <= nn; j++){cin >> tmp;mprole[name].source.insert(tmp);}}int ns; string ch, namet;for(int i = 1; i <= m; i++){ //角色关联 cin >> name >> ns;for(int j = 1; j <= ns; j++){cin >> ch >> namet;if(ch == "g")mpgroup[namet].ro.insert(name);elsemppeople[namet].ro.insert(name);}}int ng;string opt, kindt, sourcet;for(int i = 1; i <= q; i++){ //行为 cin >> name >> ng;for(int i = 1; i <= ng; i++){cin >> namet;mppeople[name].gr.insert(namet);}cin >> opt >> kindt >> sourcet;if(check(mppeople[name], opt, kindt, sourcet))cout << 1 << endl;elsecout << 0 << endl;mppeople[name].gr.clear();} return 0;
}5 PS无限版
题意：
实现点的平移，旋转，放缩，对称，投影
询问一群点的重心、到某点距离的平方和
解析：
关于投影操作，过定作垂线，交点即为投影点
过于对称操作，先求出投影点，然后平移即可
代码：
暂时有锅
202203
1 未初始化警告
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 1e5+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;int n, k;
int vis[maxn];
int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n >> k;int cnt = 0;vis[0] = 1;for(int i = 1; i <= k; i++){int x, y;cin >> x >> y;if(!vis[y])cnt++;vis[x] = 1;}cout << cnt << endl;return 0;
}2 出行计划
解析：
区间修，单点查询。
差分即可（线段树、树状数组也行）
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 1e6+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;int lowbit(int x){return x & (-x);}
int cc[maxn];
int maxx;
void insert(int x, int v){while(x <= maxx){cc[x] += v;x += lowbit(x);}
}
void update(int l, int r, int v){insert(l, v);insert(r+1, -v);
}
int query(int x){int res = 0;while(x){res += cc[x];x -= lowbit(x);}return res;
}int t[maxn], c[maxn];
int n, m, k, maxt;
//[t-k-c+1, t-k]
int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n >> m >> k;for(int i = 1; i <= n; i++){cin >> t[i] >> c[i];maxt = max(maxt, t[i]+c[i]); }maxx = maxt;for(int i = 1; i <= n; i++){if(t[i]-k < 1)continue;update(max(1, t[i]-k-c[i]+1), t[i]-k, 1);}for(int i = 1, q; i <= m; i++){cin >> q;int res = query(q);//cout << "ans = ";cout << res << endl;}return 0;
}3 计算资源调度器
题意：
大模拟
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 1e5+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;
struct node{int id;int pos;int cnt;set<int> task;node(){}node(int id, int pos, int cnt) : id(id), pos(pos), cnt(cnt){}bool operator < (const node &b) const{if(cnt == bt)return id < b.id;elsereturn cnt < bt;}
};
unordered_map<int, node> mp;
typedef unordered_map<int, node>::iterator M_IT;
typedef vector<int>::iterator V_IT;
vector<int> id;
int n, m;
void require_na(int x, vector<int> &b){ //节点亲和性for(auto it = b.begin(); it != b.end();){if(mp[*it].pos != x)b.erase(it);elseit++;}
}
void require_pa(int x, vector<int> &b){ //任务亲和性 set<int> s;//区 for(auto it = mp.begin(); it != mp.end(); it++){if((*it).se.task.count(x))s.insert((*it).se.pos);} for(auto it = b.begin(); it != b.end();){if(s.count(mp[*it].pos) == 0)b.erase(it);elseit++;}
}
vector<int> require_paa(int x, vector<int> &b){vector<int> res;for(int i = 0; i < b.size(); i++)res.push_back(b[i]); //copyfor(auto it = res.begin(); it != res.end();){if(mp[*it].task.count(x))res.erase(it);elseit++;}return res;
}
bool cmp(int a, int b){return mp[a] < mp[b];
}
int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n >> m;for(int i = 1; i <= n; i++){int pos; cin >> pos;mp[i] = node(i, pos, 0);id.push_back(i);}int T; cin >> T;while(T--){int q, a, na, pa, paa, paar;cin >> q >> a >> na >> pa >> paa >> paar;while(q--){vector<int> tmp = id;vector<int> tmp2;vector<int> res;if(na) //节点亲和性 require_na(na, tmp);if(pa) //任务亲和性 require_pa(pa, tmp);if(paa) //反亲和性 tmp2 = require_paa(paa, tmp); if(!paa) // 没有反亲和 res = tmp;else{ //有反亲和 if(tmp2.size() == 0 && paar == 0) // 尽量满足且结果空res = tmp;elseres = tmp2; } if(res.size() == 0){cout << 0 << " ";continue;} sort(res.begin(), res.end(), cmp);int nodeid = res[0]; cout << nodeid << " ";mp[nodeid]t++;mp[nodeid].task.insert(a); }cout << endl;}return 0;
}202112
1 序列查询
解析：
分段求和
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 1e5+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;ll n, N;
ll a[maxn];
ll ans;
int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n >> N;for(int i = 1; i <= n; i++)cin >> a[i];a[n+1] = N;for(int i = 0; i <= n; i++){ll cnt = a[i+1]-a[i];ans += cnt * i;;}cout << ans << endl;return 0;
}2 序列查询新解
解析：
按 f i f_i fi 分段，每一段内 f f f 值不变， g g g 单调不减。
如果 g m a x ≤ f g_{max} \le f gmax≤f 或 g m i n ≥ f g_{min} \ge f gmin≥f 直接求和即可；否则分为两段分别求和。
对 g g g 求和的时候，可以先计算前缀和
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 1e5+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;ll n, N;
ll a[maxn];
ll ans, r;
ll g(int x){return x/r;
}ll sumg(int x){ll cnt = (x+1)/r;ll res = (cnt)*(cnt-1)/2*r + (x+1)%r*cnt;return res;
}
ll cal(ll ql, ll qr, ll f){return abs(sumg(qr)-sumg(ql-1) - (qr-ql+1) * f);
}
int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n >> N;r = N/(n+1);for(int i = 1; i <= n; i++)cin >> a[i];a[n+1] = N;for(int i = 0; i <= n; i++){ll ql = a[i];ll qr = a[i+1]-1;ll f = i;if(g(qr) <= f || g(ql) >= f)ans += cal(ql, qr, f); else{int pos = r * f;ans += cal(ql, pos, f);ans += cal(pos+1, qr, f);}}cout << ans << endl;return 0;
}3 登机牌条码
题意：
大模拟
解析：
对编码数据产生数字，然后用数字产生码字。
对于校验码： x k d ( x ) ≡ q ( x ) g ( x ) − r ( x ) x^kd(x)\equiv q(x)g(x)-r(x) xkd(x)≡q(x)g(x)−r(x) ， g ( x ) g(x) g(x) 已知
所以 x k d ( x ) ≡ − r ( x ) ( m o d g ( x ) ) x^kd(x)\equiv -r(x) \:(mod\;g(x)) xkd(x)≡−r(x)(modg(x))
k k k 次多项式 g k ( k ) = g k − 1 ( x ) × ( x − 3 k ) g_k(k) = g_{k-1}(x) \times (x-3^k) gk(k)=gk−1(x)×(x−3k)
多项式除法模拟即可
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 1e5+10;
const int INF = 0x3f3f3f3f;
const int mod = 929;
typedef pair<int, int> pii;int curmode;
vector<int> number;
vector<int> code;
vector<int> verify;
vector<int> gx;
vector<int> d;
int g[2][maxn];
int w, s, vlen;
string str;ll qpow_mod(ll a, ll b){ll res = 1;while(b){if(b&1)res = res * a % mod;a = a * a % mod;b = b >> 1;}return res;
}
void putnumber(char c){if(c >= '0' && c <= '9'){if(curmode != 2){number.push_back(28); curmode = 2;}number.push_back(c-'0');}else if(c >= 'a' && c <= 'z'){if(curmode != 1){number.push_back(27);curmode = 1;}number.push_back(c-'a'); }else if(c >= 'A' && c <= 'Z'){if(curmode == 1){number.push_back(28);number.push_back(28);}if(curmode == 2)number.push_back(28);curmode = 0;number.push_back(c-'A');}
}
void get_gx(int k){memset(g, 0, sizeof(g));int cur = 1, pre = 0;g[pre][0] = -3;g[pre][1] = 1; for(int i = 2; i <= k; i++){// (x-3^i)g[cur][0] = 0;ll c = (mod - qpow_mod(3, i)) % mod;for(int j = 1; j <= k+1; j++)g[cur][j] = g[pre][j-1];for(int j = 0; j <= k+1; j++){ll tmp = (g[pre][j] * c) % mod;g[cur][j] = ((g[cur][j] + tmp) % mod + mod) % mod;}cur ^= 1;pre ^= 1;}for(int i = 0; i <= k; i++)gx.push_back(g[pre][i]);
}
void print(vector<int> &b){for(auto x : b)cout << x << " ";cout << endl;
}
void get_verify(int k){for(int i = 1; i <= k; i++)d.push_back(0);for(int i = code.size()-1; i >= 0; i--) //倒着 d.push_back(code[i]); //print(gx); //print(d);for(int i = d.size()-1; i >= k; i--){int cnt = d[i];for(int j = 0; j < gx.size(); j++){d[i-j] = d[i-j] - cnt * gx[gx.size()-1-j];d[i-j] = (d[i-j]%mod+mod)%mod;}} for(int i = k-1; i >= 0; i--){int x = (mod-d[i])%mod;cout << x << endl;}
}
int main(){ ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> w >> s;cin >> str; for(int i = 0; i < str.length(); i++)putnumber(str[i]);if(number.size()%2)number.push_back(29);code.push_back(0);for(int i = 0; i < number.size(); i += 2){int res = 30 * number[i] + number[i+1];code.push_back(res);}if(s == -1){while(code.size()%w != 0)code.push_back(900);code[0] = code.size(); for(int i = 0; i < code.size(); i++)cout << code[i] << endl;}else{vlen = qpow_mod(2, s+1);while((vlen+code.size())%w != 0)code.push_back(900);code[0] = code.size();for(int i = 0; i < code.size(); i++)cout << code[i] << endl;get_gx(vlen);get_verify(vlen);}return 0;
}更多推荐
CSP部分题题解
发布评论