\(CSP-S\)罚坐四小时赛
22.9.24
\(T1\) 欧几里得的噩梦
我一看这欧几里得不得是数论，数论哪是我能做的，然后就跳了。翻完了后三题后又滚回来了。。
大小最小：如果当前这个数可以被已选的数异或出来，那么是不必要加入的
字典序最小：从小到大扫，保证大小最小的同时就保证了字典序最小
关键是如何知道当前数能否被异或出来
一个数x有另外几个数y,z异或出来，那么y,z中并集一定包含x的1的位置，y,z的交集必须是不属于x的。
也就是如果x可以被异或出来，那么y,z一定在集合中存在并且交集非空，就是y,z是有一个连接点把这两个数连起来的，所以我们考虑并查集维护
如果有两个1，那就判断这两个1的位置；只有一个1的话，把0当成另一个1的位置
扫到一个数的时候判断是否这两个1已经在同一集合内（\(fa\)是否相同），在说明有交集，可以把不是x的1异或掉，这时这个数是不必加入的；否则，就\(merge\)并加入
异或出来的最多的数的数量就是\(2^{集合大小}\)
噩梦
#include <iostream>
#include <cstdio>
using namespace std;
inline int read(){
int x = 0, f = 1; char c;
while(!isdigit(c = getchar())) if(c == '-') f = -1;
do x = (x << 1) + (x << 3) + (c ^ 48); while(isdigit(c = getchar()));
return x * f;
}
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 5e5+5;
bool vis[N];
int n,m,fa[N],ans[N],cnt;
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
void merge(int x,int y){
if(x > y) swap(x,y);
int fx = find(x);
int fy = find(y);
fa[fy] = fx;
}
int qpow(int a,int b){
int ans = 1;
while(b){
if(b & 1) ans = ans * 1ll * a % mod;
a = a * 1ll * a % mod;
b >>= 1;
}
return ans;
}
int main(){
n = read(); m = read();
for(int i = 1; i <= m; ++i) fa[i] = i;
for(int i = 1; i <= n; ++i){
int num = read(),x = 0,y = 0;
x = read(); if(num == 2) y = read();
if(find(x) != find(y)) merge(x,y), ans[++ans[0]] = i;
}
// for(int i = 1; i <= n; ++i) if(!vis[find(i)]) vis[find(i)] = (++cnt);
// for(int i = 1; i <= n; ++i) cout << fa[i] << " "; cout << endl;
printf("%d %d\n",qpow(2,ans[0]),ans[0]);
for(int i = 1; i <= ans[0]; ++i) printf("%d ",ans[i]);
putchar('\n');
return 0;
}
\(T2\) 清扫
每个叶子节点的石头如果被清掉，有两种方式：1.和子树内的另一个叶子组合 2.和子树外的另一个叶子组合
第一种方式会让根节点清掉一个石头，该子树内清掉两个石头
第二种方式会让根节点清掉一个石头，该子树内清掉一个石头
第一种方式的操作数我们设为x次，第二种方式的操作数我们设为y次，该子树的根设为u，该根内所有儿子需要与外部叶子组合的石头总和为sum，该子树内所有儿子需要与外部叶子组合的石头的最大值为max
那么我们可以得出以下柿子：
\(x + y = a[u]\)
\(2 \times x + y = sum\)
解方程得到
\(x = sum - a[u]\)
\(y = 2 \times a[u] - sum\)
限制就是\(x \geq 0\), \(y \geq 0\)
还有一个限制就是 \(max \leq a_u\)
因为子树内的点无论是在内部还是在外部操作，都会经过根节点（这个子树内的根）
码
#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
const int N = 2e5+5;
inline int read(){
int x = 0, f = 1; char c;
while(!isdigit(c = getchar())) if(c == '-') f = -1;
do x = (x << 1) + (x << 3) + (c ^ 48); while(isdigit(c = getchar()));
return x * f;
}
int n,a[N],f[N],du[N];
struct Edge{int to,nxt;}e[N << 1];
int head[N],tot;
void add(int u,int v){
e[++tot] = (Edge){v,head[u]};
head[u] = tot;
}
void dfs(int u,int fa){
if(du[u] == 1) {f[u] = a[u]; return;}
int sum = 0, mmax = 0;
for(int i = head[u]; i; i = e[i].nxt){
int v = e[i].to;
if(v == fa) continue;
dfs(v,u);
sum += f[v];
if(mmax < f[v]) mmax = f[v];
}
if(sum - a[u] < 0 || 2 * a[u] - sum < 0 || mmax > a[u]) {puts("NO"); exit(0);}
f[u] += 2 * a[u] - sum;
}
signed main(){
n = read();
for(int i = 1; i <= n; ++i) a[i] = read();
for(int i = 1; i < n; ++i){
int u = read(),v = read();
add(u,v); add(v,u);
du[u]++; du[v]++;
}
if(n == 2){
if(a[1] == a[2]) puts("YES");
else puts("NO");
exit(0);
}
int root = 1;
for(int i = 1; i <= n; ++i) if(du[i] > 1){
root = i; break;
}
dfs(root,0);
if(f[root]) puts("NO");
else puts("YES");
return 0;
}
\(T3\) 购物
结论题，求前缀和进行合并即可
(瞎说几句)如果我们可以拼凑出价格x，那么\([\lceil \frac{x}{2} \rceil,x]\)中的数一定是美妙的
我们的价格和价格可以拼凑，所以我们考虑美妙的数的范围能否合并
我们把一个价格抽象成一个一维线段，其中*代表中点
如果两个范围可以直接合并，有两种情况：
- 交叉
-----------*-------------
------------------*--------------------
短线段的右端点在长线段的范围内，可以直接合并区间，并且把价格累加重新扩大右边界
对于小数的右边界到大数的左边界这段范围为什么会被覆盖到，我认为可以这样考虑
一个数\(x = \frac{x}{2} + \frac{x}{2}\)，这个式子显然正确
我们设当前价值总和为\(sum\),\(sum = \frac{sum}{2} + \frac{sum}{2}\),短线段设为x，长线段设为y,x+y的值是确定的，当x=y时，中间没有空隙，可以直接合并；如果x!=y，那么必定x,y中有一个数是大于\(\frac{sum}{2}\)，那么这段空隙照样可以被覆盖。
- 包含
--------*--------
------------------------*------------------------
然后就可以写了
其实求前缀和这个操作是我拿对拍拍出来的
码
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define int long long
using namespace std;
const int N = 1e5+5;
inline int read(){
int x = 0, f = 1; char c;
while(!isdigit(c = getchar())) if(c == '-') f = -1;
do x = (x << 1) + (x << 3) + (c ^ 48); while(isdigit(c = getchar()));
return x * f;
}
int n,a[N];
void solve(){
int ans = 0,sum = 0,L,R;
L = ceil((double)a[1] / 2);
R = a[1]; sum = a[1];
for(int i = 2; i <= n; ++i){
int x = ceil((double)a[i] / 2);
int y = a[i];
if(R >= x && L <= x);
else{
ans += (R - L + 1);
L = x;
}
sum += a[i]; R = sum;
}
printf("%lld\n",ans + R - L + 1);
}
signed main(){
n = read();
for(int i = 1; i <= n; ++i) a[i] = read();
sort(a + 1, a + 1 + n);
solve();
return 0;
}
\(T4\) 还没改出来
22.9.25
\(T1\) 回文
列\(dp\)式子
因为是回文，所以我们需要两头兼顾，为了好表述，我们假设\(A\)在\((1,1)\)的位置开始走，\(B\)在\((n,n)\)的位置开始走，\(AB\)同时走
\(dp_{i,j,k,s}\)表示当前\(A\)在\((i,j)\)的位置，\(B\)在\((k,s)\)的位置时所走过的（现在的判断其实是间断的）回文路径的数量
发现\(i+j+k+s=n+m+2\)时的状态才会有用，所以我们可以优化掉一维
然后开写就行了
点击查看代码
#include <iostream>
#include <cstdio>
const int N = 505;
const int mod = 993244853;
int n,m,f[N][N][N],ans;
char c[N][N];
int main(){
scanf("%d%d",&n,&m);
for(register int i = 1; i <= n; ++i) scanf(" %s ",c[i] + 1);
f[1][1][n] = (c[1][1] == c[n][m]);
for(register int i = 1; i <= n; ++i){
for(register int j = 1; j <= m; ++j){
for(register int k = 1; k <= n; ++k){
int s = n + m + 2 - i - j - k;
if(s < 1 || s > m) continue;
if(c[i][j] != c[k][s]) continue;
if(i - 1 >= 1 && k + 1 <= n){
f[i][j][k] += f[i - 1][j][k + 1];
if(f[i][j][k] >= mod) f[i][j][k] -= mod;
}
if(i - 1 >= 1 && s + 1 <= m){
f[i][j][k] += f[i - 1][j][k];
if(f[i][j][k] >= mod) f[i][j][k] -= mod;
}
if(j - 1 >= 1 && k + 1 <= n){
f[i][j][k] += f[i][j - 1][k + 1];
if(f[i][j][k] >= mod) f[i][j][k] -= mod;
}
if(j - 1 >= 1 && s + 1 <= m){
f[i][j][k] += f[i][j - 1][k];
if(f[i][j][k] >= mod) f[i][j][k] -= mod;
}
if((i == k && j == s) || (i == k && j + 1 == s) || (i + 1 == k && j == s)){
ans += f[i][j][k];
if(ans >= mod) ans -= mod;
}
}
}
}
printf("%d\n",ans);
return 0;
}
\(T2\) 快速排序
打完之后感觉像模拟题
点击查看代码
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 5e5+5;
const int INF = 1111114514;
int T,n,a[N],b[N],cur,cnt;
void solve(int L){
if(L > n) return;
if(cnt == n) return;
// cout << "\na? " << L << " " << a[L] << " " << b[cur] << " " << cnt << endl;
if(a[L] == INF){
cnt++;
printf("nan ");
solve(L + 1);
return;
}
if(cur && a[L] < b[cur]) {solve(L + 1); return;}
for(++cur; b[cur] < a[L] && cur <= n; ++cur) printf("%d ",b[cur]),cnt++;
printf("%d ",a[L]); cnt++;
solve(L + 1);
}
int main(){
// freopen("T.in","r",stdin);
// freopen("T.out","w",stdout);
scanf("%d",&T);
while(T--){
scanf("%d",&n); cur = cnt = 0;
for(int i = 1; i <= n; ++i) a[i] = 0;
for(int i = 1; i <= n; ++i){
scanf("%d",&a[i]);
if(!a[i]){
getchar(); getchar(); getchar();
a[i] = INF;
}
}
for(int i = 1; i <= n; ++i) b[i] = a[i];
// for(int i = 1; i <= n; ++i) cout << a[i] << " "; cout << endl;
sort(b + 1, b + 1 + n);
solve(1); putchar('\n');
}
return 0;
}
\(T3\) 混乱邪恶
\(n^2\)暴搜，理论时间复杂度不允许我们\(A\)掉，但是数据允许（误
不会正解，看不懂题解，听不懂证明，正解请见此
点击查看代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6+6;
int n,m,c[N],sum,tmp;
struct node{int v,id;}a[N];
bool operator < (const node &x,const node &y){return x.v < y.v;}
signed main(){
srand(time(0));
scanf("%lld%lld",&n,&m);
for(int i = 1; i <= n; ++i) scanf("%lld",&a[i].v),a[i].id = i,sum += a[i].v;
sort(a + 1, a + n + 1);
sum >>= 1; tmp = sum;
for(int j = n; j > 0; --j){
for(int i = 1; i <= n; ++i) c[i] = 0;
c[a[n - j].id] = -1; sum = tmp - a[n - j].v;
for(int i = n; i > 0; --i){
if(i == n - j) continue;
if(sum >= a[i].v){
sum -= a[i].v;
c[a[i].id] = -1;
}
}
if(sum == 0){
puts("NP-Hard solved");
for(int i = 1; i <= n; ++i) printf("%d ",c[i] == 0 ? 1 : -1);
putchar('\n'); return 0;
}
}
puts("Chaotic evil");
return 0;
}
\(T4\) 毒瘤数据结构，狗都不改
主要是不会
标签：const,int,sum,ans,include,CSP,mod From： https://www.cnblogs.com/Facrt/p/16726766.html