首页 > 其他分享 >1600-1900 题单1

1600-1900 题单1

时间：2023-02-25 14:44:19浏览次数：56  
标签：return NO int 1600 cin long 题单 1900 define

构造题单

A

题目链接

这个题目的切入点很不好找，首先我们可以假设我们已经构造出来了t字符串，并且它的不同字符的个数是cnt。那么我们可以知道\(\frac{n}{cnt}的含义是每一组相同字符的个数\)。

那么根据题目的意思是不是我们需要s串和t串相匹配的字符尽可能地多。假设at['a']表示是‘a'字符的出现的次数，这个时候我们只需要和\(\frac{n}{cnt}\)取一个最小值得出来了限制之后的值。

这个值就是某一个字符可以匹配的最长的长度，至于k我们for一下就好了因为最大值只有可能26，这也是时间复杂度控制的关键。

然后怎么替换多的字符以及增加少的字符呢，这里有一个贪心的思路：那就是我们先从那些出现次数多的字符串开始枚举，因为如果这个字符多了可以将其分配给别的字符，如果这个字符少了可以原地增加就好了。

下面解释下order的作用：他就是上面的按照某个字母出现的次数对字符排序。

这个题目还需要好好实现下代码，一点都不熟练。

#include<bits/stdc++.h>

using namespace std;

void solve()
{
	int n;
	cin>>n;
    string s;
    cin>>s;
    vector<vector<int>> at(36);
    for(int i=0;i<n;i++){
    	at[(int)(s[i]-'a')].push_back(i);
    }	
    vector<int> order(26);
    iota(order.begin(),order.end(),0);
    sort(order.begin(),order.end(),[&](int i,int j){
    	return at[i].size()>at[j].size();
    });
    string res="";
    int best=-1;
    for(int cnt=1;cnt<=26;cnt++)
    {
    	if(n%cnt==0)
    	{
    		int cur=0;
    		for(int i=0;i<cnt;i++)
    		{
    			cur+=min(n/cnt,(int)at[order[i]].size());
    		}
    		if(cur>best)
    		{
    			best=cur;
    			res=string(n,' ');
    			vector<char> extra;
    			for(int it=0;it<cnt;it++)
    			{
    				int i=order[it];
    				for(int j=0;j<n/cnt;j++)
    				{
    					//就说明还有数字需要填。
    					if(j<(int)at[i].size())
    					{
    						res[at[i][j]]=(char)('a'+i);
    					}
    					else
    					{
    						extra.push_back((char)('a'+i));
    					}
    				}
    			}
    			for(char& c:res)
    			{
    				if(c==' '){
    					c=extra.back();
    					extra.pop_back();
    				}
    			}
    		}
    	}
    }
    cout<<n-best<<endl;
    cout<<res<<endl;
	
}


int main()
{
   int T;
   cin>>T;
   while(T--)
   {
   	solve();
   }
   
   
}

B

核心思路

这个其实就是一个很通用的构造方法。首先我们可知道的是我们肯定是需要构造出相邻的数对不超过m的数列。可以参考这种构造方式：\(a[n],a[1],a[n-1],a[2],...\)

前提是需要进行逆序排序。

然后找出来不满足条件的逆序对，这个就可以使用二分了。写check的时候使用双指针扫一遍就好了。

// Problem: D. Watch the Videos
// Contest: Codeforces - 2022-2023 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules, Preferably Teams)
// URL: https://codeforces.com/problemset/problem/1765/D
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define NO {puts("NO") ; return ;}
#define YES {puts("YES") ; return ;}
#define endl "\n"
#define int long long 

const int N=1e6+10;
int n,m;
int sum;
int a[N];

int check(int x)
{
	int l=x-1,r=n-1;
	while(l<r)
	{
		if(a[l]+a[r]>m)
		return 0;
		l++;
		if(l<r)
		{
			if(a[l]+a[r]>m)
			return 0;
			r--;
		}
	}
	return 1;
}

signed main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
	cin>>a[i];
	sum+=a[i];
}

sort(a,a+n,greater<int>());
int l=1,r=n;//主意好边界不可能是0的。
while(l<r)
{
	int mid=l+r>>1;
	if(check(mid))
	r=mid;
	else
	l=mid+1;
	
}
cout<<sum+r<<endl;
return 0;




}

C

核心思路

待补，没有看懂什么。

题目

题解

// Problem: D. Permutation Addicts
// Contest: Codeforces - Codeforces Global Round 22
// URL: https://codeforces.com/problemset/problem/1738/D
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define NO {puts("NO") ; return ;}
#define YES {puts("YES") ; return ;}
#define endl "\n"
#define int long long
const int N=2e5+10; 
vector<int> v[N];
vector<int> a;
int n,b[N],k;

void solve()
{
	cin>>n;
	k=0;
	a.clear();
	for(int i=0;i<=n+1;i++)
	v[i].clear();
	for(int i=1;i<=n;i++)
	{
		cin>>b[i];
		k+=b[i]>i;
		v[b[i]].push_back(i);
	}
	int cur=0;//cur表示的是b数组里面的数.
	if(v[n+1].size())
	cur=n+1;
	int cnt=0;
	while(cnt<n)
	{
		cnt+=v[cur].size();
		for(auto &it:v[cur])
		{
			if(v[it].size())
			swap(it,v[cur].back());
		}
		a.insert(a.end(),v[cur].begin(),v[cur].end());
		cur=v[cur].back();
		
	}
	cout<<k<<endl;
	for(auto it:a)
	cout<<it<<" ";
	cout<<endl;
}


signed main()
{
int T;
cin>>T;
while(T--)
{
	solve();
}
}

D

核心思路

这个题目肯定首先需要对式子化简把：

$concat(A_i,A_j) \ mod \ 3=(A_i*10^k+A_j) \ mod\ 3=(A_i+A_j) \mod \ 3 $

然后根据题意我们可以把最终的式子化简为：\(A_i^2+A_j^2=Z mod \ 3\)

再就是另外一个重要的结论：

\(任何一个平方数模3的余数只有可能是0和1.不可能是2\\我们根据这个性质可以比较方便的确定出来Z的一个取值范围\)

x表示的是\(A_imod\ 3\)这个数组中0的个数，y表示的是1的个数。

  1. x>y,那么我们就把1全部都染成一种颜色，这样就不可能出现2了。
  2. x<y，那么我们就把0全部都染成一种颜色，这样就不可能出现0了。
// Problem: H. Hot Black Hot White
// Contest: Codeforces - COMPFEST 14 - Preliminary Online Mirror (Unrated, ICPC Rules, Teams Preferred)
// URL: https://codeforces.com/problemset/problem/1725/H
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define NO {puts("NO") ; return ;}
#define YES {puts("YES") ; return ;}
#define endl "\n"
#define int long long 

const int N=1e6+10;
char s[N];

signed main()
{
int n;
cin>>n;
vector<int> a(n+1);
for(int i=1;i<=n;i++)
cin>>a[i];
vector<int> b(n+1);
string t;
for(int i=1;i<=n;i++)
{
	b[i]=a[i]*a[i]%3;
	t.push_back('0'+b[i]);
}
//cout<<t<<endl;
int x=count(t.begin(),t.end(),'0');
int y=count(t.begin(),t.end(),'1');
//cout<<x<<" "<<y<<endl;
int cnt_0=0;
int cnt_1=0;
string ans;
if(x>y)
{
	for(auto x:t)
	{
		if(x=='0')
		{
			if(cnt_0<n/2)
			{
				cnt_0++;
				ans.push_back('0');
			}
			else if(cnt_1<n/2)
			{
				cnt_1++;
				ans.push_back('1');
			}
		}
		else
		{
			if(cnt_1<n/2)
			{
				ans.push_back('1');
				cnt_1++;
			}
			else if(cnt_0<n/2)
			{
				ans.push_back('0');
				cnt_0++;
			}
		}
	}
	cout<<2<<endl;
	cout<<ans<<endl;
}
else
{
	for(auto x:t)
	{
		if(x=='1')
		{
			if(cnt_1<n/2)//千万需要注意边界.
			{
				cnt_1++;
				ans.push_back('1');
			}
			else if(cnt_0<n/2)
			{
				cnt_0++;
				ans.push_back('0');
			}
		}
		else
		{
			if(cnt_0<n/2)
			{
				ans.push_back('0');
				cnt_0++;
			}
			else if(cnt_1<n/2)
			{
				ans.push_back('1');
				cnt_1++;
			}
		}
	}
	cout<<0<<endl;
	cout<<ans<<endl;
}


}

E

题目链接

这个其实首先应该联想我们的常用的构造方法：

先分奇数和偶数

然后一个普遍的思路就是先放奇数再放偶数，但是我们可以发现先要把2和4先放了。

其实这个都是观察第三个构造发现的规律。

// Problem: G. Special Permutation
// Contest: Codeforces - Codeforces Round #640 (Div. 4)
// URL: https://codeforces.com/contest/1352/problem/G
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define NO {puts("NO") ; return ;}
#define YES {puts("YES") ; return ;}
#define endl "\n"
#define int long long 


void solve()
{
	int n;
	cin>>n;
	if(n<4)
	{
		cout<<-1<<endl;
		return;
	}
	for(int i=n;i>=1;i--)
	{
		if(i&1)
		cout<<i<<" ";
	}
	cout<<4<<" "<<2<<" ";
	for(int i=6;i<=n;i+=2)
	cout<<i<<" ";
	cout<<endl;
	
}

signed main()
{
int T;
cin>>T;
while(T--)
{
	solve();
}
}

F

核心思路

题目链接

这个题目其实主要是一个模拟，刚开始我想用双指针模拟，然后发现那个区间长度不是很好处理。

因此我们可以使用set来对我们的区间长度进行拍排序。

这里有个很重要的关于set的语法，使用结构体进行处理。

// Problem: D. Constructing the Array
// Contest: Codeforces - Codeforces Round #642 (Div. 3)
// URL: https://codeforces.com/contest/1353/problem/D
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define NO {puts("NO") ; return ;}
#define YES {puts("YES") ; return ;}
#define endl "\n"
#define int long long 

struct cmp{
	bool operator() (const pair<int,int>& a,const pair<int,int> &b)const{
		int lena=a.second-a.first+1;
		int lenb=b.second-b.first+1;
		if(lena==lenb)
		return a.first<b.first;
		return lena>lenb;
	}
};


void solve()
{
	int n;
	cin>>n;
	set<pair<int,int>,cmp> segs;
	segs.insert({0,n-1});
	vector<int> a(n);
	for(int i=1;i<=n;i++)
	{
		pair<int,int> cur=*segs.begin();
		segs.erase(segs.begin());
		int id=(cur.first+cur.second)/2;
		a[id]=i;
		if(cur.first<id)
		segs.insert({cur.first,id-1});
		if(id<cur.second)
		segs.insert({id+1,cur.second});
	}
	for(auto it: a)
	cout<<it<<" ";
	cout<<endl;
	
	
}


signed main()
{
int t;
cin>>t;
while(t--)
{
	solve();
}
}

G

核心思路

这个题目我们一个很通用的思维是经可能的构造出来的1，但是这里数据范围是很大的。所以我们肯定不可以使用for循环的方式把1给解出来。

所以我们假设前面的k-3段都是1，那么后面的三个数的和就是\(n-k+3\).然后我们就看n-k+3可以分解为哪三个数。

很显然先分奇偶分解:

  1. n为奇数，这个可以分为{1,n/2,n/2},并且最大公约数是n/2;
  2. n为偶数，这个就要注意了，我们如果分解为{2,n/2-1,n/2-1},那么这个的最大公约数是n-2,所以需要小于等于n/2，那么n就必须小于4.所以我们还得增加一个n%4的分类讨论。
// Problem: C2. k-LCM (hard version)
// Contest: Codeforces - Codeforces Round #708 (Div. 2)
// URL: https://codeforces.com/contest/1497/problem/C2
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define NO {puts("NO") ; return ;}
#define YES {puts("YES") ; return ;}
#define endl "\n"
#define int long long 

vector<int> solve3(int n){
	if(n%2==1)
	return {1,n/2,n/2};
	if(n%4==0)
	return {n/2,n/4,n/4};
	if(n%2==0)//这里的限制是n小于等于4.
	return {2,n/2-1,n/2-1};
}


void solve()
{
	int n,k;
	cin>>n>>k;
	vector<int> added=solve3(n-k+3);
	for(int i=0;i<k;i++)
	cout<<(i<3?added[i]:1)<<" ";
	cout<<endl;
	
}


signed main()
{
int t;
cin>>t;
while(t--)
{
	solve();
}
}

H

核心思路

首先我们可以先把所有的坏人的位置给找出来，然后给他的四周加上墙壁。然后就是最关键的地方。

我们直接从终点往回搜索，只要遇到不是墙壁的都给他打上标记。然后我们就只要看，好人是否被打上了标记，以及坏人是否没有标记。

G

核心思路

这个题目的思路确实不太容易想到。

  1. 首先特判n==1，

    1 1
0
1 1
0
1 1
-a1

  2. 然后就是n不等于1的情况

    1 1
-a1
1 n
0 -n*a2 -n*a3 ..... -n*an
2 n
(n-1)a2 (n-1)a3 ..... (n-1)an

// Problem: A. Multiples of Length
// Contest: Codeforces - Codeforces Round #666 (Div. 1)
// URL: https://codeforces.com/contest/1396/problem/A
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define NO {puts("NO") ; return ;}
#define YES {puts("YES") ; return ;}
#define endl "\n"
#define int long long 


signed main()
{
int n;
cin>>n;
vector<int> a(n+1);
for(int i=1;i<=n;i++)
cin>>a[i];

if(n==1)
{
	cout<<1<<" "<<1<<endl;
	cout<<0<<endl;
	cout<<1<<" "<<1<<endl;
	cout<<0<<endl;
	cout<<1<<" "<<1<<endl;
	cout<<-a[1]<<endl;
}
else
{
	cout<<1<<" "<<1<<endl;
	cout<<-a[1]<<endl;
	cout<<1<<" "<<n<<endl;
	cout<<0<<" ";
	for(int i=2;i<=n;i++)
	cout<<-n*a[i]<<" ";
	cout<<endl;
	cout<<2<<" "<<n<<endl;
	for(int i=2;i<=n;i++)
	cout<<(n-1)*a[i]<<" ";
	cout<<endl;
}


}

标签：return,NO,int,1600,cin,long,题单,1900,define
From： https://www.cnblogs.com/xyh-hnust666/p/17154380.html

相关文章

  • 点分治练习题单（动态更新）
    传送门有点难，慢慢做。1.P2634[国家集训队]聪聪可可比板子要简单一点，分治时寻找路径时用桶记录模数为\(0,1,2\)的个数，再进行\(01\)背包即可。统计答案时由于两点可......
  • Circle of Monsters[*1600][暴力][构造]
    CircleofMonsters[*1600][暴力][构造]Problem-C-Codeforces有\(N\)头怪兽，他们围成一个环，顺时针编号\(1,2,3,4,\dots,N\)每一头怪兽都有2个属性，一个是它的生......
  • 周六1900C++班级-2023.2.19-字符串string
    字符串练习使用string定义一个字符串变量strings;字符串是单引号的（×）整行输入字符串有三种方式，分别是gets(),getline(cin,str),cin.getline(str,100)（√）gets是字符数......
  • 1600 - 请假时间计算
         ......
  • 洛谷oj题单【入门2】分支结构-入门难度（Java）
    洛谷oj题单【入门2】分支结构-入门难度（Java）来源：https://www.luogu.com.cn/training/101#problemsP5709【深基2.习6】ApplesPrologue/苹果和虫子importjava.util.Sc......
  • 洛谷oj题单【入门1】顺序结构-入门难度（Java）
    洛谷oj题单【入门1】顺序结构-入门难度（Java）来源：https://www.luogu.com.cn/training/100#problemsB2002Hello,World!publicclassMain{  publicstaticvoidmain......
  • CF构造题1600-1800（2）
    H.HotBlackHotWhite(COMPFEST14-PreliminaryOnlineMirror(Unrated,ICPCRules,TeamsPreferred))题意有\(n\)个石头，每个石头有一个值\(a_i\)，现在需要给这......
  • CF构造题1600-1800（1）
    D.SameCountOne(PolynomialRound2022(Div.1+Div.2,Rated,Prizes!))题意给定\(n\)个长度为\(m\)的01序列，每次操作可以选择两个序列a1,a2，并选择一个\(p......
  • CF1771C 质数分解+思维技巧题 *1600 (普及+/提高)
    Problem-1771C-Codeforces有 T 组数据，每组数据给出 n 和长度为 n的数列 a[i]​，判断有没有两个数不互质，如果有输出"YES"，没有输出"NO"n≤2e51≤a[i]≤1e9难......
  • kuangbin题单|基础dp
    1.HDU1024MaxSumPlusPlus最大M子段和\(dp[i][j]\)表示以第j个数结尾且被分为i段的最大子段和，答案即是\(dp[m][n]\)。与单集合（\(m=1\)）的最大字段和不同的点在于，本题......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99