首页 > 其他分享 >Codeforces Round 968 (Div. 2)

Codeforces Round 968 (Div. 2)

时间:2024-09-02 23:25:11浏览次数:11  
标签:cout int 968 Codeforces cin maxn ans Div define

vp的,老规矩跳过ab

C:

根据题意我们知道三个不一样的字母连续放一定可以,然后观察样例发现好像把两个不同的字母轮流放也可以。进一步猜测(瞎猜的)发现这个好像只要把不同的挨个放进去就行了(本来以为可能要按数量排序但是似乎根本不用),最后剩下的全放一起也没事。然后就过了。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
vector<int>E[maxn];
bool vis[maxn];
void dfs(int u,int fa){
	if(E[u].size()==1&&E[u][0]==fa){
		vis[u]=1;
		//cout<<u<<"mk\n";
		return;
	}
	for(int i:E[u])	if(i!=fa)dfs(i,u);
}
int a[maxn];
map<char,int>mp;
set<char>st;
signed main() {
	ios::sync_with_stdio(false);
	// ½â³ýcinºÍcoutµÄĬÈϰ󶨣¬À´½µµÍIOµÄ¸ºµ£Ê¹Ð§ÂÊÌáÉý
	cin.tie(NULL); cout.tie(NULL);
	int t; cin >> t;
	while (t--) {
		int n;cin>>n;mp.clear();st.clear();
		string s,ans="";
		cin>>s;
		for(int i=0;i<s.size();i++){
			mp[s[i]]++;st.insert(s[i]);
		}
		while(ans.size()<s.size()){
			for(char j:st){
				if(mp[j])mp[j]--,ans+=j;
			}
		}
		cout<<ans<<"\n";
	}
}

D:

D1

对每个序列可以取多次意思就是可以取到第二个没出现过的最小整数。然后根据ans和m的关系进行数学计算即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5+10;
int a[maxn];
vector<int>E[maxn];
signed main() {
	ios::sync_with_stdio(false);
	// ½â³ýcinºÍcoutµÄĬÈϰ󶨣¬À´½µµÍIOµÄ¸ºµ£Ê¹Ð§ÂÊÌáÉý
	cin.tie(NULL); cout.tie(NULL);
	int t; cin >> t;
	while (t--) {
		int n,m;cin>>n>>m;
		for(int i=0;i<=n;i++)E[i].clear();
		for(int i=1;i<=n;i++){
			cin>>a[i];
			for(int j=1;j<=a[i];j++){
				int x;cin>>x;
				E[i].push_back(x);
			}
			sort(E[i].begin(),E[i].end());
		}
		int ans=0;
		for(int i=1;i<=n;i++){
			int nw=0;
			for(int j=0;j<a[i];j++){
				if(E[i][j]==nw)nw++;
			}
			nw++;
			for(int j=0;j<a[i];j++){
				if(E[i][j]==nw)nw++;
			}
			ans=max(ans,nw);
		}
		//cout<<ans<<"MK\n";
		if(ans>=m){
			ans=ans*(m+1);
		}
		else{
			int tmp=ans;
			ans=ans*(ans+1);
			ans=ans+(tmp+m+1)*(m-tmp)/2;
		}
		cout<<ans<<"\n";
	}
}

D2:

总觉得暴力优化能过。但是并不能。

建图,每个序列只会贡献一条边,由最小未出现值到第二小未出现值建边,每个点出边的数量表示能一次操作到达该点的序列数。所以对于点x,若x出边大于2,则f[x]任意点都可达,否则只有点x可达。

f[x]最小为x。从最大值k开始倒叙dp维护f[x],同时维护t(由出边大于2的点的\(f_max\)贡献)

最终一个点的值就是max(f[x],t),复杂度为线性

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define mkp make_pair
#define fir first
#define sec second
#define pb push_back
const int maxn = 2e5+100;
int f[maxn],a[maxn];
pii b[maxn];
vector<int>E[maxn];

signed main() {
	ios::sync_with_stdio(false);
	// 解除cin和cout的默认绑定,来降低IO的负担使效率提升
	cin.tie(NULL); cout.tie(NULL);
	int t; cin >> t;
	while (t--) {
		int k=0,t=0,sum=0;
		int n,m;cin>>n>>m;
		for(int i=1;i<=n;i++){
			cin>>a[0];
			for(int j=1;j<=a[0];j++)cin>>a[j];
			sort(a+1,a+a[0]+1);
			int nw=0,j=1;
			while(nw>=a[j]&&j<=a[0]){
				if(nw==a[j])nw++;
				j++;
			}
			int u=nw;nw++;t=max(u,t);
			while(nw>=a[j]&&j<=a[0]){
				if(nw==a[j])nw++;
				j++;
			}
			int v=nw;b[i]=mkp(u,v);
			//cout<<u<<' '<<v<<endl;
			k=max(v,k);
		}
		for(int i=0;i<=k;i++)f[i]=0,E[i].clear();
		for(int i=1;i<=n;i++){
			E[b[i].fir].pb(b[i].sec);
		}
		for(int i=k;i>=0;i--){
			f[i]=i;
			for(int j:E[i])f[i]=max(f[i],f[j]);
			if(E[i].size()>=2)t=max(t,f[i]);
		}
		for(int i=0;i<=min(k,m);i++){
			f[i]=max(f[i],t);
			sum+=f[i];
		}
		if(k<m)sum+=(k+1+m)*(m-k)/2;
		cout<<sum<<"\n";
	}
}

标签:cout,int,968,Codeforces,cin,maxn,ans,Div,define
From: https://www.cnblogs.com/lyrrr/p/18393738

相关文章

  • Codeforces Round 970 div3
    CodeforcesRound970div3错过的一场比赛,第二天早晨VP,题目的通过率还挺奇怪A.Sakurako'sExamhttps://codeforces.com/contest/2008/problem/A题意:有a个1和b个2的数组,在1和2前面增添加减号,判断是否能让结果为0思路:1个2需要2个1进行填补,不如先让2自己进行消去,如......
  • Codeforces Round 969 Div.2+Div.1
    A.Dora'sSet注意到任意两个偶数的\(\gcd\)都大于\(1\),因此选择的三个数中至多一个偶数,而注意到相邻的奇数一定互质,因此每次选两个奇数一个偶数,答案=奇数的个数÷2点击查看代码#include<bits/stdc++.h>usingnamespacestd;#definelllonglong#defineullunsigned......
  • codeforces做题记录(1924B)& 回顾线段树
    1924B.SpaceHarbour题意:n个点排成一行,其中某些点上面建有港湾,港湾有一个权值,对每个点我们定义点的权值为“左边(包括自己)第一个港湾上的权值\(\times\)到右边(包括自己)第一个港湾的距离”(保证在一开始1号和n号点上都有港湾)。有q次操作:操作1给定x和v,表示在x点上建立权值为v的......
  • Codeforces Round 969 (Div. 2)
    ab题没啥好说的,b题一开始看题错成线段树了,后面发现维护最大值就过了(我就说b怎么会有线段树)。。。C:DoraandC++卡的我死死的,好久没卡c了,数论果然是最短板。。。我有两个推论,但是一个都不会用:1.翡蜀定理。(但是这题只有正数)(处理两个数的情况)2.断环为链。(但是我只会n方,即以每个......
  • codeforces写题随录 ##1
    菜鸡刷题比赛日记之数学知识相关[https://codeforces.com/contest/2007/problem/C](C.DoraandC++)这题包含加A和加B,此处应该先考虑特殊情况a=b,若不进行如何操作的话,初始答案应该是res=a[n]-a[1](排序之后),然后进行操作,想想该如何最小化极差。为了便于计算,先将数组中每个数字......
  • Diffusion反馈强势助力CLIP秒变火眼金睛:北京智源研究院、中科院自动化所联合推出DIVA
    前言 本文分享论文DiffusionFeedbackHelpsCLIPSeeBetter,专注于通过自监督学习范式解决CLIP无法区分细粒度视觉细节的问题。欢迎关注公众号CV技术指南,专注于计算机视觉的技术总结、最新技术跟踪、经典论文解读、CV招聘信息。本文转载自我爱计算机视觉仅用于学术分享,若侵权......
  • Codeforces Round 873 (Div. 2)
    ABC都很简单,但是D1写起来有些麻烦,就没写,D2应该是一个分治的思路,后面想不出来了。D1的思路非常好出,n只有5e3的范围,意味着\((n^2)\)可过,可以直接枚举所有的子区间,也就是题目所说的子数组,然后尝试统计答案。考虑一个子区间的答案是什么样的,发现只有逆序的数字才需要排序,我们直接找......
  • CF1980F1 & F2 Field Division
    前言纪念一下独立做出来的\(2400\)的题Easyversion思路先说\(Easy\)版本的我们走路的方式只有可能是这种样子:(出处:luoguuserFiraCode)不想手绘图了即对列排序后,所形成的一个行编号上升的序列所以\(Easy\)就很简单了,对于每一列的最大值,如果大于当前前缀最大值,则......
  • Educational Codeforces Round 169 (Rated for Div. 2)
    A.ClosestPoint有解的情况,当且仅当只有两个点且不相邻是,把新加入的点放在中间。#include<bits/stdc++.h>usingnamespacestd;usingi32=int32_t;usingi64=longlong;usingi128=__int128;#defineinti64usingvi=vector<int>;usingpii=pair<int,int......
  • codeforces做题记录(1942D,1938J,1934D1,1933F)
    1942D.LearningtoPaint题目大意:给定一行白格子,可以将任意的格子染成黑色,最终形成多个黑色的连续段,对每个连续段[i,j]有一个权重(题目给定),为aij,每个染色方案的权值就是所有连续段的权值的和。要求所有染色方案中前k大的权值。注意事项:权重aij的范围是[-1e6,1e6],格子个数n<=10......