首页 > 其他分享 >CF1709 题解

CF1709 题解

时间：2022-12-04 11:56:00浏览次数：71  
标签：int 题解 1ll CF1709 maxn mod include define

比赛链接：https://codeforces.com/contest/1709

题解：
AB
水题

// by SkyRainWind
#include <cstdio>
#include <vector>
#include <cassert>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define pii pair<int,int>

using namespace std;

typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f;

void solve(){
	int x;scanf("%d",&x);
	int a[5];
	for(int i=1;i<=3;i++)scanf("%d",&a[i]);
	int cnt=1;
	while(1){
		if(a[x]){
			++ cnt;
			int tmp = a[x];
			a[x] = 0;
			x = tmp;
		}else break;
	}
	if(cnt == 3)puts("YES");
	else puts("NO");
}

signed main(){
	int te;scanf("%d",&te);
	while(te--)solve();

	return 0;
}

// by SkyRainWind
#include <cstdio>
#include <vector>
#include <cassert>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define pii pair<int,int>

using namespace std;

typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f,maxn=2e5+5;
int n,m,a[maxn];
LL sum[maxn],sum2[maxn];
signed main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=2;i<=n;i++){
		sum[i] = sum[i-1];
		if(a[i] < a[i-1])sum[i] += a[i-1] - a[i];
	}
	for(int i=n-1;i>=1;i--){
		sum2[i] = sum2[i+1];
		if(a[i] < a[i+1])sum2[i] += a[i+1]-a[i];
	}
	while(m--){
		int x,y;scanf("%d%d",&x,&y);
		if(x<y)printf("%I64d\n",sum[y]-sum[x]);
		else printf("%I64d\n",sum2[y]-sum2[x]);
	}

	return 0;
}

C
题目保证一定存在解，观察可知开始的?全填( 一定是一个解
然后考虑是否存在第二个解，显然把最后一个'('换成')'再判断是否有解即可（因为如果还有其它解的话，这个解一定被包含在内）

// by SkyRainWind
#include <cstdio>
#include <vector>
#include <cassert>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define pii pair<int,int>

using namespace std;

typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f, maxn=2e5+5;

char s[maxn];
void solve(){
	scanf("%s", s+1);
	int n=strlen(s+1);
	int a1=0,a2=0;
	for(int i=1;i<=n;i++)
		if(s[i] == '(')++ a1;
		else if(s[i] == ')')++ a2;
	a1 = n/2 - a1, a2 = n/2 - a2;
	if(a1 == 0 || a2 == 0){
		puts("YES");
		return ;
	}
	int fg = 1;
	for(int i=1;i<=n;i++){
		if(s[i] == '?'){
			if(a1 == 1 && fg){
				if(a2)s[i] = ')', -- a2, fg = 0;
				else s[i] = '(', -- a1;
			}else{
				if(a1)s[i] = '(', -- a1;
				else s[i] = ')', -- a2;
			}
		}
	}
	int tmp = 0; 
	for(int i=1;i<=n;i++)
		if(s[i] == '(')++ tmp;
		else{
			-- tmp;
			if(tmp < 0){
				puts("YES");
				return ;
			}
		}
	puts("NO");
}

signed main(){
	int te;scanf("%d",&te);
	while(te--)solve();

	return 0;
}

D
显然xy独立，先判一下y之间距离是否为k的倍数
接着看能否“上去”，利用st表维护一下区间max，看起点往上走k的倍数步且超过max之后是否会出边界
我把st表写错了。。(int)log(1.0 * (r-l+1)) / log(2.0)是错误的！！！

// by SkyRainWind
#include <cstdio>
#include <vector>
#include <cassert>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mpr make_pair
#include <cmath>
#define debug() cerr<<"Yoshino\n"
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define pii pair<int,int>

using namespace std;

typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f, maxn = 1e6+5;

int n,m;
int a[maxn], st[maxn][22];

int query(int l,int r){
	int j = (int)(log(1.0 * (r-l+1)) / log(2.0));
	return max(st[l][j], st[r-(1<<j)+1][j]);
}

signed main(){
	scanf("%d%d",&m,&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),st[i][0] = a[i];
	for(int j=1;j<=19;j++)
		for(int i=1;i+(1<<j)-1<=n;i++)
			st[i][j] = max(st[i][j-1], st[i+(1<<(j-1))][j-1]);
	int qe;scanf("%d",&qe);while(qe--){
		int x1,y1,x2,y2,k;
		scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&k);
		if(y1 > y2)swap(y1, y2), swap(x1, x2);
		if(x1 == x2 && y1 == y2){
			puts("YES");
			continue;
		}
		int dcol = y2 - y1;
		if(dcol % k != 0 || abs(x1-x2) %k != 0){
			puts("NO");
			continue;
		}
		int mx = query(y1, y2);
		int tp = (m - x1) / k * k + x1;
		if(tp > mx)puts("YES");
		else puts("NO");
	}

	return 0;
}

E
首先一条路径 \((u,v)\) 的异或和可以化为 \(d[u] \ xor\ d[v] \ xor\ a[lca]\) ，其中 \(d[u]\) 是 \(u\) 到 1 路径的异或和
考虑对一个点，维护其子树内有多少种 \(d\) ，这显然可以用 set 维护
然后往当前点 \(x\) 添加子树 \(u\) 的时候，可以使用启发式合并。如果遇到 \(u\) 的子树中有 \(d[v]\) ，而且 \(d[v] \ xor\ a[x]\) 出现在 \(x\) 的set中，那么说明 \(x\) 的子树中存在某一点 \(w\) ，\(w \rightarrow v\) 的权值异或和是 0，因此需要修改 \(x\) 的权值（显然这是最优的方案），因为可以任意修改，所以可以保证对于 \(x\) 的子树中只修改1次就可以了，也就是说在添加完 \(x\) 的所有子树后把 \(x\) 的set清空

// by SkyRainWind
#include <cstdio>
#include <vector>
#include <cassert>
#include <cstring>
#include <iostream>
#include <set>
#include <algorithm>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define pii pair<int,int>

using namespace std;

typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f, maxn = 2e5+5;

int n, a[maxn];
vector<int>g[maxn];
set<int>S[maxn];
int xo[maxn];

void dfs0(int x,int fat=0){
	xo[x] ^= a[x];
	for(int u : g[x])if(u!=fat){
		xo[u] ^= xo[x];
		dfs0(u, x);
	}
}

int ans = 0;
void dfs(int x,int fat=0){
	int gg = 0;
	S[x].insert(xo[x]);
	for(int u : g[x])if(u!=fat){
		dfs(u, x);
		if(S[u].size() > S[x].size())swap(S[x], S[u]);
		// combine u to x
		for(int i : S[u])if(S[x].count(i ^ a[x])){gg = 1;break;}
		for(int i : S[u])S[x].insert(i);
	}
//	printf("%d %d\n",x,gg);
//	for(int i : S[x])printf("%d ",i);debug();
	if(gg){
		++ ans;
		S[x].clear();
	}
}

signed main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=n-1;i++){
		int x,y;scanf("%d%d",&x,&y);
		g[x].push_back(y), g[y].push_back(x);
	}
	dfs0(1);
	dfs(1);
	printf("%d\n",ans);

	return 0;
}

F
注意到出现了前缀，而且字符串又挺多，考虑 01 trie
发现对于某个01串的 \(c_s\) 限制，可以转化为该01串在trie上的点，比如 \(x\)，则 \(fa[x] \rightarrow x\) 的容量即为 \(c_s\)，题目要求的就是从源点开始跑最大流，所有叶子为汇点，最大流为 \(f\) 的方案数，我们只需要给边赋容量即可
考虑树形dp，因为同层的点都是等价的，所以只需要考虑 \(n\) 个结点即可
设 \(dp[x][i]\) 表示考虑到第 \(x\) 结点，\(x\) 及 \(x\) 子树这块连通块能流过的流量为 \(i\) 的赋值方案数
则有$$dp[x][i] = \sum_{j,k}$$$$ (dp[s1][j] \times dp[s2][k], 如果 j+k>i) $$$$ (dp[s1][j] \times dp[s2][k] * (k-i+1),如果 j+k=i)$$
\(s1, s2\) 为 \(x\) 的两个儿子
理解一下就是第一种情况，必须要限制 \(fa[x] \rightarrow x\) 这条边的容量为 \(i\) 才能满足状态，因此只有一种情况，第二种情况只要 \(fa[x] \rightarrow x\) 大于等于 \(i\) 即可，有 \((k-i+1)\) 种情况
又发现实际上 \(dp[s1]\) 和 \(dp[s2]\) 也是等价的，因此相当于自己和自己卷积就是一个转移
第一种情况，卷积完求个后缀和。第二种情况也同理
代码中的\(F[j] G[j]\)实际上就是当前 i 的 \(dp[i][j]\)
注意一下最后还需要转移一下，\(F=F*F\) 之后求 \(F[f]\) 就是流量恰好为 \(f\) 的情况
时间复杂度 \(O(nk \log k)\)

// by SkyRainWind
#include <cstdio>
#include <vector>
#include <cassert>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define pii pair<int,int>

using namespace std;

typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f, mod =998244353;

int pw(int a, int b)
{
    int res = 1;
    while(b) {
        if(b & 1) res = 1ll * res * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1;
    }
    return res;
}

namespace Poly
{
	const int N = 2000007;
    #define mul(x, y) (1ll * x * y >= mod ? 1ll * x * y % mod : 1ll * x * y)
    #define minus(x, y) (1ll * x - y < 0 ? 1ll * x - y + mod : 1ll * x - y)
    #define plus(x, y) (1ll * x + y >= mod ? 1ll * x + y - mod : 1ll * x + y)
    #define ck(x) (x >= mod ? x - mod : x)//取模运算太慢了

    typedef vector<int> poly;
    const int G = 3;//根据具体的模数而定，原根可不一定不一样！！！
    //一般模数的原根为 2 3 5 7 10 6
    const int inv_G = pw(G, mod - 2);
    int RR[N], deer[2][21][N], inv[N];

    void init(const int t) {//预处理出来NTT里需要的w和wn，砍掉了一个log的时间
        for(int p = 1; p <= t; ++ p) {
            int buf1 = pw(G, (mod - 1) / (1 << p));
            int buf0 = pw(inv_G, (mod - 1) / (1 << p));
            deer[0][p][0] = deer[1][p][0] = 1;
            for(int i = 1; i < (1 << p); ++ i) {
                deer[0][p][i] = 1ll * deer[0][p][i - 1] * buf0 % mod;//逆
                deer[1][p][i] = 1ll * deer[1][p][i - 1] * buf1 % mod;
            }
        }
        inv[1] = 1;
        for(int i = 2; i <= (1 << t); ++ i)
            inv[i] = 1ll * inv[mod % i] * (mod - mod / i) % mod;
    }

    int NTT_init(int n) {//快速数论变换预处理
        int limit = 1, L = 0;
        while(limit <= n) limit <<= 1, L ++ ;
        for(int i = 0; i < limit; ++ i)
            RR[i] = (RR[i >> 1] >> 1) | ((i & 1) << (L - 1));
        return limit;
    }

    void NTT(poly &A, int type, int limit) {//快速数论变换
        A.resize(limit);
        for(int i = 0; i < limit; ++ i)
            if(i < RR[i])
                swap(A[i], A[RR[i]]);
        for(int mid = 2, j = 1; mid <= limit; mid <<= 1, ++ j) {
            int len = mid >> 1;
            for(int pos = 0; pos < limit; pos += mid) {
                int *wn = deer[type][j];
                for(int i = pos; i < pos + len; ++ i, ++ wn) {
                    int tmp = 1ll * (*wn) * A[i + len] % mod;
                    A[i + len] = ck(A[i] - tmp + mod);
                    A[i] = ck(A[i] + tmp);
                }
            }
        }
        if(type == 0) {
            for(int i = 0; i < limit; ++ i)
                A[i] = 1ll * A[i] * inv[limit] % mod;
        }
    }

    poly poly_mul(poly A, poly B) {//多项式乘法
        int deg = A.size() + B.size() - 1;
        int limit = NTT_init(deg);
        poly C(limit);
        NTT(A, 1, limit);
        NTT(B, 1, limit);
        for(int i = 0; i < limit; ++ i)
            C[i] = 1ll * A[i] * B[i] % mod;
        NTT(C, 0, limit);
        C.resize(deg);
        return C;
    }
}
//using namespace Poly;

int n,k,f;

signed main(){
	scanf("%d%d%d",&n,&k,&f);
	if(f > 2*k)return puts("0"), 0;
	vector<int>F(k+1, 1);
	Poly::init(20);
	for(int i=1;i<=n-1;i++){
		vector<int>G = Poly::poly_mul(F,F), tmp = G;
		for(int j = G.size() - 2;j >= 0; j--)(G[j] += G[j+1]) %= mod;	// 后缀和 第一种情况 
		for(int j=0;j<G.size();j++){
			if(j > k)G[j] = 0;	// 流量最大就是 k 了，超过 k 就没有意义了 
			else (G[j] += 1ll * tmp[j] * (k-j) % mod)%= mod;	// tmp[j]*(k-j) 就是第二种情况，注意G[]已经改了所以用tmp 
		}
		F = G;
		F.resize(k + 1);
	}
	F = Poly::poly_mul(F, F);
	printf("%d\n",F[f]);

	return 0;
}

标签：int,题解,1ll,CF1709,maxn,mod,include,define
From： https://www.cnblogs.com/SkyRainWind/p/16949572.html

相关文章

  • AtCoder Beginner Contest 280 题解
    A-PawnonaGrid看样例猜题意（要求的是#的数量，直接判断。//If,oneday,Ifinallymanagetomakemydreamsareality...//Iwonder,willyoustillbethere......
  • YACS 2022年11月月赛 乙组 T3 菜单设计 题解
    题目链接上完编程课回来的深夜，更一篇吧。这一题一看数据范围$:18$，阶乘暴力打不了，就是状压。其实我还是比较喜欢状压的，不过这几个月怎么这么多状压？首先：设计状态不难发......
  • 树上染色-题解（贪心+DP+二分）
    树的上色题意简述树上有两个黑点，在每个单位时间内，每个黑点可以把自己相邻的一个白点变为黑色，求把整棵树所有点变为黑色的最短时间。\(n\)个点，两个黑点分别为\(x,y\)。......
  • 2022合肥学院acm程序设计大赛-热身赛题解 (1)
    A.codeforces直接读入输入即可#include<bits/stdc++.h>intmain(){strings;cin>>s;cout<<"https://codeforces.com/profile/"<<s;return0;}......
  • 合肥学院校赛热身赛题解
    A.codeforces直接读入输入即可#include<bits/stdc++.h>intmain(){strings;cin>>s;cout<<"https://codeforces.com/profile/"<<s;return0;}......
  • [SCOI2014]方伯伯的玉米田题解
    [SCOI2014]方伯伯的玉米田题目描述方伯伯在自己的农田边散步，他突然发现田里的一排玉米非常的不美。这排玉米一共有\(N\)株，它们的高度参差不齐。方伯伯认为单调不下降序......
  • Ynoi2011题解
    d1t1初始化题意一个长度为\(n\)的序列,\(q\)次操作。询问\([l,r]\)的区间和。将所有\(\bmodx=y\)的下标位置加\(z\)。\(n,q\leq2\times10^5\)。题解......
  • CF1710 题解
    比赛链接：https://codeforces.com/contest/1711BD比以往的要难，E要更简单A水题//bySkyRainWind#include<cstdio>#include<vector>#include<cassert>#include<c......
  • 问题解决系列：从源码讲解为什么是 'JZ0SL_ Unsupported SQL type 1111'
    一、问题场景正在做代码改造，使用​​mybatis​​​+​​sybase​​进行数据库操作，运行过程中，提示以下报错：java.io.IOException:JZ0SL:UnsupportedSQLtype1111.本篇博客......
  • npm 报错：npm ERR! Maximum call stack size exceeded 超过最大栈问题解决方案
    先尝试将npm升级到最新版1234$npminstallnpm-g#检查版本$npm-v6.14.5运行以下命令删除当前路径下的node_modules目录1234$rmnode_mo......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99