首页 > 其他分享 >CF1783 A-F 题解

CF1783 A-F 题解

时间：2023-01-10 22:46:30浏览次数：52  
标签：typedef return CF1783 int 题解 long maxn define

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

连续三场出4题，还行（其实感觉有两场的E都是会做的）

A
水题

// by SkyRainWind
#include <bits/stdc++.h>
#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;
typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f;
int n,a[200005];
int cmp(int a,int b){return a>b;}
void solve(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	sort(a+1,a+n+1,cmp);
	if(a[1] == a[2])swap(a[2], a[n]);
	if(a[1] == a[2])return (void)puts("NO");
	puts("YES");
	for(int i=1;i<=n;i++)printf("%d ",a[i]);puts("");
}

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

	return 0;
}

B
考虑蛇形构造，像这样：
1 9 2
6 5 8
4 7 3

// by SkyRainWind
#include <bits/stdc++.h>
#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;
typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f;
int n,a[55][55];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int in(int x,int y){
	if(x>=1&&x<=n&&y>=1&&y<=n&&a[x][y]==0)return 1;
	return 0;
}
void solve(){
	scanf("%d",&n);
	memset(a,0,sizeof a);
	a[1][1] = 1;
	int x=1,y=1,curx=0;
	int now=1,de=n*n-1;
	for(int i=2;i<=n*n;i++,--de){
		if(i%2==0)now+=de;
		else now-=de;
		if(in(x+dx[curx],y+dy[curx])){
			x += dx[curx], y += dy[curx];
			a[x][y] = now;
		}else{
			curx = (curx+1)%4;
			x += dx[curx], y += dy[curx];
			a[x][y] = now;
		}
	}
	for(int i=1;i<=n;i++,puts(""))
		for(int j=1;j<=n;j++)printf("%d ",a[i][j]);
}

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

	return 0;
}

C
二分排名 x，然后判断一下能不能和原来排名为 x 的人比一比

// by SkyRainWind
#include <bits/stdc++.h>
#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;
typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f,maxn=5e5+5;
int n,m;
struct node{
	int v,id;
}a[maxn],b[maxn];
int cmp(node a,node b){
	return a.v<b.v;
}
int check(int rk){
	int im = n-rk+1;
	int mm = m, now = 0;
	for(int i=1;i<=n;i++)
		if(mm - a[i].v >= 0){
			mm -= a[i].v;
			++ now;
		}else break;
	if(now >= im)return 1;
	
	if(m < b[im].v)return 0;
	mm = m - b[im].v, now = 1;
	for(int i=1;i<=n;i++){
//		printf("! %d %d\n",im,a[i].id);
		if(a[i].id == im)continue;
		if(mm - a[i].v >= 0){
			mm -= a[i].v;
			++ now;
		}else break;
	}
	if(now >= im-1)return 1;
	return 0;
}
void solve(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i].v), a[i].id = i;
	for(int i=1;i<=n;i++)b[i] = a[i];
	sort(a+1,a+n+1,cmp);
	int l=1,r=n,ans=n+1;
	while(l<=r){
		int mid=l+r>>1;
		if(check(mid))r=mid-1,ans=mid;
		else l=mid+1;
	}
	printf("%d\n",ans);
}

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

	return 0;
}

D

考虑dp，设 \(dp[i][S]\) 表示考虑到第 \(i\) 个位置，此处现在的值是 \(S\) 的方案数
\(dp[i][S] \rightarrow dp[i+1][S+a[i+1]] or dp[i+1][a[i+1]-S]\)，注意一下可能有负数，另外如果 S 是0的话只能转移其中一个
有负数所以第二维 +一个大数 就行了，这里偷懒用了unordered_map，贴时限过的（不过卡这个的人也真是sxbk）

// by SkyRainWind
#include <bits/stdc++.h>
#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;
typedef long long LL;

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

int n,a[maxn];
unordered_map<int,int>dp[2];

signed main(){
//	freopen("D.in","r",stdin);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	dp[2&1][a[2]] = 1;
	for(int i=2;i<=n-1;i++){
		dp[i+1&1].clear();
		for(auto pr : dp[i&1]){
			int lstt = pr.first, dpp = pr.second;
			(dp[i+1&1][lstt + a[i+1]] += dp[i&1][lstt]);
			if(dp[i+1&1][lstt+a[i+1]]>=mod)dp[i+1&1][lstt+a[i+1]]-=mod;
			
			if(lstt == 0)continue;
			(dp[i+1&1][a[i+1] - lstt] += dp[i&1][lstt]) %= mod;
		}
	}
	ll ans=0;
	for(auto pr : dp[n&1])
		(ans += pr.second) %= mod;
	cout<<ans;

	return 0;
}

E
当时过了D之后就摆了，结果仔细一看我会做。。
考虑什么样的 \(k\) 符合条件：\((m-1)k<a[i]<=mk \and (m-1)<b[i]\)，对任意 \(i\) 成立
首先，如果 \(a[i]<=b[i]\) 那么任意的 \(k\) 都一定符合条件，故只考虑 \(a[i] > b[i]\)
注意到一开始的条件就等价于 \([b[i],a[i])\) 不能有 \(k\) 的倍数
直接 枚举 \(k\) 计算即可，复杂度是调和级数
（另外直接暴力分解质因数也是可以过的）

// by SkyRainWind
#include <bits/stdc++.h>
#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;
typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f, maxn = 2e5+5;
int n,a[maxn],b[maxn],cf[maxn];
set<int>ban;
void cutdiv(int x){
	for(int i=1;i*i<=x;i++)
		if(x%i == 0)
			ban.insert(i), ban.insert(x/i);
}
void solve(){
	ban.clear();
	scanf("%d",&n);
	for(int i=0;i<=n+1;i++)cf[i] = 0;
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)scanf("%d",&b[i]);
	
	for(int i=1;i<=n;i++)
		if(a[i] > b[i])
			++ cf[b[i]], -- cf[a[i]];
	
	for(int i=2;i<=n;i++)
		cf[i] += cf[i-1];
	vector<int>vi;
	for(int k=1;k<=n;k++){
		int gg = 0;
		for(int i=k;i<=n;i+=k)
			if(cf[i]){gg = 1;break;}
		if(!gg)vi.push_back(k);
	}
	printf("%d\n",vi.size());
	for(int u : vi)printf("%d ",u);puts("");
}

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

	return 0;
}

F
对于一个排列而言，如果 \(i->p[i]\) 连一条有向边，那么这个排列排好的步数就是 所有环的(size-1)之和
也就是说，对于一个环，让其中一个元素不动，其它元素都动
然后考虑怎么拓展到2个排列
首先发现，要求的是使操作数最小，也就是使不变的元素最多。考虑最多有多少个元素不变
由于一个环中有且仅有一个元素不变，因此如果固定住了一个元素不变，那么在两个排列中分别对应的这个元素所在的环都只能让这一个元素不变（其它的元素的并集就不能选了）。因此如果将一个排列上的每个环与另一个排列的环连边（如果存在一个 \(i\) 使得两个环都含有 \(i\) 的话），容易发现这是个二分图，而所求的最多个不变元素就是这个图的最大匹配，网络流解决

// LUOGU_RID: 99283169
// by SkyRainWind
#include <bits/stdc++.h>
#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;
typedef long long LL;

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

template<class T>
struct Flow {
    const int n;
    struct Edge {
        int to;
        T cap;
        Edge(int to, T cap) : to(to), cap(cap) {}
    };
    std::vector<Edge> e;
    std::vector<std::vector<int>> g;
    std::vector<int> cur, h;
    Flow(int n) : n(n), g(n) {}
    
    bool bfs(int s, int t) {
        h.assign(n, -1);
        std::queue<int> que;
        h[s] = 0;
        que.push(s);
        while (!que.empty()) {
            const int u = que.front();
            que.pop();
            for (int i : g[u]) {
                auto v=e[i].to, c=e[i].cap;
                if (c > 0 && h[v] == -1) {
                    h[v] = h[u] + 1;
                    if (v == t) {
                        return true;
                    }
                    que.push(v);
                }
            }
        }
        return false;
    }
    
    T dfs(int u, int t, T f) {
        if (u == t) {
            return f;
        }
        auto r = f;
        for (int &i = cur[u]; i < int(g[u].size()); ++i) {
            const int j = g[u][i];
            auto v=e[j].to, c=e[j].cap;
            if (c > 0 && h[v] == h[u] + 1) {
                auto a = dfs(v, t, std::min(r, c));
                e[j].cap -= a;
                e[j ^ 1].cap += a;
                r -= a;
                if (r == 0) {
                    return f;
                }
            }
        }
        return f - r;
    }
    void addEdge(int u, int v, T c) {
        g[u].push_back(e.size());
        e.emplace_back(v, c);
        g[v].push_back(e.size());
        e.emplace_back(u, 0);
    }
    T maxFlow(int s, int t) {
        T ans = 0;
        while (bfs(s, t)) {
            cur.assign(n, 0);
            ans += dfs(s, t, std::numeric_limits<T>::max());
        }
        return ans;
    }
};

int n,a[maxn],b[maxn],bela[maxn],belb[maxn];

signed main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)scanf("%d",&b[i]);
	memset(bela,-1,sizeof bela);
	memset(belb,-1,sizeof belb);
	
	for(int i=1;i<=n;i++)
		if(~bela[i])continue;
		else{
			int j = i;
			while(bela[j] == -1){
				bela[j] = i;
				j = a[j];
			}
		}
	for(int i=1;i<=n;i++)
		if(~belb[i])continue;
		else{
			int j = i;
			while(belb[j] == -1){
				belb[j] = i;
				j = b[j];
			}
		}
	
	Flow<int> flow(2*n + 3);
	for(int i=1;i<=n;i++)
		flow.addEdge(bela[i], n + belb[i], 1);
	for(int i=1;i<=n;i++)
		flow.addEdge(2*n+1, i, 1),
		flow.addEdge(n+i, 2*n+2, 1);
	flow.maxFlow(2*n+1, 2*n+2);
	vector<int>ans;
	for(int i=0;i<n;i++)
		if(flow.e[2*i].cap)ans.push_back(i + 1);
	printf("%d\n",ans.size());
	for(int u : ans)printf("%d ",u);puts("");
		
	return 0;
}

标签：typedef,return,CF1783,int,题解,long,maxn,define
From： https://www.cnblogs.com/SkyRainWind/p/17041298.html

相关文章

  • 「JOI Open 2022」Giraffes 题解
    设我们将要给出的观感好的排列为\(q\)，我们希望求出\(\sum[p_i=q_i]\)的最大值（这里指不移动的长颈鹿个数）。结论一：当且仅当左右端点有当前区间最大值或者最小值时条件才......
  • 题解1
    离散化1.为什么要离散化当数据很大的时候，以至于我们不能直接使用它的时候，就要考虑将其用另外一种形式表达,通常是将其映射为数组下标。2.离散化本质本质:映射3.离......
  • charls抓包的乱码问题解决
    1.在charls的安装目录下，去修改配置文件的值----Charles.ini，内容如下   2.SSLproxysetting设置如下图  3.顺便说一下，charls抓取https的包，一定要先安......
  • docker中crontab无法执行导入计划任务问题解决
    问题描述：crontab无法执行导入计划任务解决： ⊙查看文件16进制 hexdump-c./crontab/defalut   发现有\r；crontab中只能直接\n⊙vim文件修改编码   setfile......
  • P3521 题解
    非线段树合并做法。复杂度多一只log，但是好写。跳过不重要的部分，直达核心——如何在递归时计算两棵子树互相的贡献？题解区清一色线段树合并从值域角度考虑。但是显然倍......
  • [IOI2000]邮局 题解
    简要题意线段上有\(V\)个村庄，现在要建\(P\)个邮局，使每个村庄到最近的邮局的距离之和最小。50分做法设\(dp[i][j]\)表示第一个村庄到第\(i\)个村庄，建了\(j\)个......
  • mysql delete大量数据表锁死，kill的线程后线程处于killed状态问题解决
    一、事件起因删除一张500G的表，没有添加任何约束条件，结果好久都没反应，查询锁之后，使用kill杀掉了进程，再次查询的时候，锁还在，trx_state的状态是ROLLINGBACK，使用showprocessl......
  • 网络流二十四题解题报告
    网络流二十四题解题报告\(\text{ByDaiRuiChen007}\)来源：LOJ-网络流24题机器人路径规划问题数据有误，不计入解题报告中1.飞行员配对方案问题ProblemLink构造二......
  • hidapi 编译成 dll 时出现无法解析外部符号问题解决方法
    问题现象：  解决方法： ......
  • Codeforces 1704 F Colouring Game 题解 (结论，SG函数)
    题目链接首先看R和B的数量不等的情况(很多博弈题都是先比较两种物品的数量，相等的情况再用SG函数之类的技巧)，结论是R多Alice必赢，B多Bob必赢。证明：来看R比B多的情况，定义两人......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99