本文共 5037 字，大约阅读时间需要 16 分钟。

A. Anti-knapsack

因为在$[k+1,n]$内的数肯定可以拿,这里有$n-k$个数

而在$[1,k]$内的数,我们只拿走在$[\frac{(k+1)}{2},k-1]$内的数字

所以加起来,我们拿了$n-\frac{(k+1)}{2}$个数字

考虑这样做为什么是对的

首先我们知道$1$和$k-1$不能同时拿

类似的$2$和$k-2$不能同时拿,$3$和$k-3$不能同时拿…

所以我们可以把$[1,k-1]$分成$\frac{k-1}{2}$组,每组内部不能同时拿

这样至少有$\frac{k-1}{2}$个数拿不到(当$k-1$是奇数时中间那个数不分组,因为它可以拿)

所以$[1,k-1]$最多拿走$(k-1)-\frac{k-1}{2}$个数

然后$[k+1,n]$全拿,这样最大是$(n-k)+(k-1)-\frac{k-1}{2}=n-\frac{k+1}{2}$

然后发现我们一开始构造的就是最优解。

#include 
   
    using namespace std;const int maxn = 3e5+10;int n,k;int main(){
   	int t; cin >> t;	while( t-- )	{
   		cin >> n >> k;		cout << n-(k+1)/2 << endl;		for(int i=(k+1)/2;i<=n;i++)		{
   			if( i!=k )	cout << i << " ";		}		cout << endl;	}}
   

B. Planet Lapituletti

暴力,没什么好说的

#include 
   
    using namespace std;const int maxn = 3e5+10;string s;int a[6],h,m;//���������int zhuan(int x){
   	if( x==1 )	return 1;	if( x==2 )	return 5;	if( x==3 )	return -1;	if( x==4 )	return -1;	if( x==5 )	return 2;	if( x==6 )	return -1;	if( x==7 )	return -1;		if( x==8 )	return 8;	if( x==9 )	return -1;} bool isok(){
   	a[1] = zhuan( s[4]-'0' );	a[2] = zhuan( s[3]-'0' );	a[3] = zhuan( s[1]-'0' );	a[4] = zhuan( s[0]-'0' );	if( a[1]==-1||a[2]==-1||a[3]==-1||a[4]==-1 )	return false;	int x = a[1]*10+a[2];	int y = a[3]*10+a[4];//	cout << "��˵ʲô\n";	if( x>=h||y>=m )	return false;	return true;}int main(){
   	int t; cin >> t;	while( t-- )	{
   		cin >> h >> m >> s ;		int sum = ( s[0]-'0' )*10+(s[1]-'0');		sum = sum*m;		sum += ( s[3]-'0' )*10+( s[4]-'0' );	//	cout << sum << endl;		for(int i=sum;;i++)		{
   			if( i==h*m ){
    cout << "00:00\n"; break; }			int x = i/m, y = i%m;			s[0] = x/10+'0', s[1] = x%10+'0';			s[3] = y/10+'0', s[4] = y%10+'0';			if( isok() )			{
   		//		cout << "??????\n";				for(int j=0;j<=4;j++)	cout << s[j];				cout << endl;				break;			}		}	}}
   

1493 C. K-beautiful Strings

转自官方题解

我们最好的答案是和原串$s$相等

如果达不到,就看一下前$n-1$个字母是否能相等,如果还达不到就看一下前$n-2$个字母能不能相等…

于是我们从后往前枚举第$k$个位置,判断$[1,k-1]$和原串相等,在第$k$个位置大于原串是否可行

基于这个贪心准则,我们计算一个$cnt[i]$表示$[1,k-1]$中字母$i$的出现次数

然后计算一个$sum$表示如果$[1,k-1]$和原串相等,最少需要补齐多少个字母变成$k$的倍数

$sum=\sum _{i=0}^{25}(k-cnt[i]\%k)\%k$

但是第$k$位比原串大,但是具体放哪个字母呢??

我们可以把这个字母贪心的从$s[k]+1$枚举到${}^{\prime }{z}^{\prime }$,看最好能放哪个字母

在第$k$位放字母$w$,显然需要更新$sum$,此时如果$i+sum<=n$说明是可行的

因为第$k$位比较大,已经保证了字典序比较大,后续只需要满足字母是$k$的倍数即可

没有填满的部分全部填${}^{\prime }{a}^{\prime }$即可

因为n是k的倍数,前面填充的部分用sum补齐了,所以也是k的倍数。

那么剩下的部分也一定是k的倍数,所以贪心放a没有问题

#include 
   
    using namespace std;const int maxn = 3e5+10;int cnt[27],n,k;string s;int get(int x){
    return (k-x%k)%k; }int main(){
   	int t; cin >> t;	while( t-- )	{
   		cin >> n >> k >> s;		for(int i=0;i
    
     =0;i--)			{
   				sum = sum-get( cnt[s[i]-'a'] )+get( --cnt[s[i]-'a'] );				for(int j=s[i]-'a'+1;j<=25;j++)//枚举放哪个字母				{
   					int las = sum;					sum = sum-get( cnt[j] )+get( ++cnt[j] );					if( (i+1)+sum<=n )					{
   						for(int pos=0;pos
    
   

D. GCD of an Array

动态维护每一个质因子的最小值,相乘就是答案.

因为每次只乘上一个数,一个数的质因子最多只有$log(n)$个

所以整体质因子只有$nlog(n)$个,空间复杂度足够

我们可以开一个二维$map$记作$mp[i][j]$表示$a[i]$中有多少质因子$j$

再开一个$multiset$记作$cnt[i]$

$cnt[i]$里面的数是每个$a[i]$拥有的质因子$i$个数,如果质因子是$0$就不插入了

那么如果$cnt[i]$里有$n$个数,说明所有的数都有$i$这个质因子

那么$cnt[i].begin()$就是所有数中最少的$i$的质因子,$i^{cnt[i].begin()}$就是质因子$i$的贡献

所以每次插入$x$,对$x$分解质因子,动态维护$mp[][]$,然后动态维护$cnt$即可

主要是利用了$multiset$平衡树的特性,动态给数值排序第一个数最小

#include 
   
    using namespace std;#define int long longconst int maxn = 3e5+10;const int mod = 1e9+7;map
    
     mp[maxn];multiset
     
      cnt[maxn];int nxt[maxn],n,q,ans=1;void add(int i,int x){
   	while( x!=1 )	{
   		int div = nxt[x], add = 0;		while( nxt[x]==div )	add++, x=x/nxt[x];				int now = mp[i][div];//之前有多少div这个质因子 		mp[i][div] += add;		int mi = 0;//之前所有数的最小质因子数量 		if( cnt[div].size()==n )	mi = (*cnt[div].begin() );		if( now )	cnt[div].erase( cnt[div].find(now) );//抹掉原来的因子 		cnt[div].insert( now+add );//加上现在的因子 		if( cnt[div].size()==n )//计算质因子的贡献 		{
   			int mx = (*cnt[div].begin() );			for(int j=mi+1;j<=mx;j++)	ans = ans*div%mod;		}	}}signed main(){
   	cin >> n >> q;	for(int i=2;i
      
       10000 )	continue;			for(int j=i+i;j
       
        > x, add(i,x);	for(int i=1;i<=q;i++)	{
   		int l,x; cin >> l >> x;		add(l,x);		cout << ans << "\n";	}}
       
      
     
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/114490112 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！