Codeforces Round #694 (Div. 1)

A.Strange Birthday Party
给定m个物品和价值,保证非递减,每个物品只能被选择一次,有n个人,每个人有一个k,代表他只能选择编号小于等于k的物品,或者直接花费\(c_k\),求最少总花费。
考虑贪心,让k最大的人选择最前面的物品,这样无法选择物品的人都是k较小的,这样其选择花费\(c_k\)也比较优。

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=3e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
int k[N],c[N];
int vis[N];
void work()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
    	scanf("%d",&k[i]);
    }
    for(int i=1;i<=m;i++){
    	scanf("%d",&c[i]);
    	vis[i]=0;
    }
    sort(k+1,k+n+1);
    int now=1;
    ll ans=0;
    for(int i=n;i>=1;i--){
    	while(now<=m&&vis[now]){
    		now++;
    	}
    	if(now==m+1){
    		ans+=c[k[i]];
    	}else{
    		if(now<=k[i]){
    			ans+=c[now];
    			vis[now]=1;
    		}else{
    			ans+=c[k[i]];
    		}
    	}
    }
    printf("%lld\n",ans);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

B.Strange Definition
定义相邻为\(lcm(a_i,a_j)/gcd(a_i,a_j)\)为完全平方数(包括自己),在每一秒,每个数会变成与其相邻数的乘积,记\(d_i\)为与第i个数相邻的数的数量,每次询问第x秒\(max(d_{\sum_{i=1}^n d_i})\)
可以发现,对于一些相邻的数,如果有偶数个,那么过去一秒后其会变成完全平方数,使得所有完全平方数都相邻,如果有奇数个,获得的乘积中奇数个的质因数还是那几个,还是只有这些数相邻。所以只需要区分0秒和其他时间。如何快速求某个数相邻的数量,考虑每个数中偶数个的质因数都无用,只考虑保留奇数个的质因子,且只保留一个,那么相邻的数都会变成相同的数,用一个数组记录即可。0秒时即为这个数组中的最大值,1秒时要记录所有偶数个相邻数的和(注意1也是完全平方数,奇数时也加入),与奇数个相邻数求最大值即可。

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=1e6+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
int prime[N];
int pri[N];
int tot=0;
int a[N];
int vis[N];
void pre(int n)
{
	tot=0;
	prime[1]=1;
	for(int i=2;i<=n;i++){
		if(!prime[i]){
			pri[++tot]=i;
		}
		for(int j=1;j<=tot&&i*pri[j]<=n;j++){
			prime[i*pri[j]]=1;
			if(i%pri[j]==0)break;
		}
	}
}
void work()
{
    int n;
    scanf("%d",&n);
    int sum=0;
    int ans=0;
    int ans2=0;
    for(int i=1;i<=n;i++){
    	scanf("%d",&a[i]);
    	int x=a[i];
    	int tmp=1;
    	for(int j=1;j<=tot&&1ll*j*j<=x;j++){
    		if(x%pri[j]==0){
    			int cnt=0;
    			while(x%pri[j]==0){
    				x/=pri[j];
    				cnt^=1;
    			}
    			if(cnt==1){
    				tmp*=pri[j];
    			}
    		}
    	}
    	if(x!=1){
    		tmp*=x;
    	}
    	//printf("%lld\n",tmp);
    	vis[tmp]++;
    	ans=max(ans,vis[tmp]);
    	ans2=max(ans,vis[tmp]);
    	if(vis[tmp]%2==0){
    		sum+=vis[tmp];
    	}else{
    		sum-=vis[tmp]-1;
    	}
    }
    if(vis[1]%2==1){
    	sum+=vis[1];
    }
    ans2=max(ans2,sum);
    int q;
    scanf("%d",&q);
    for(int i=1;i<=q;i++){
    	ll x;
    	scanf("%lld",&x);
    	if(x==0){
    		printf("%d\n",ans);
    	}else{
    		printf("%d\n",ans2);
    	}
    }
    for(int i=1;i<=n;i++){
    	//scanf("%d",&a[i]);
    	int x=a[i];
    	int tmp=1;
    	for(int j=1;j<=tot&&1ll*j*j<=x;j++){
    		if(x%pri[j]==0){
    			int cnt=0;
    			while(x%pri[j]==0){
    				x/=pri[j];
    				cnt^=1;
    			}
    			if(cnt==1){
    				tmp*=pri[j];
    			}
    		}
    	}
    	if(x!=1){
    		tmp*=x;
    	}
    	//printf("%lld\n",tmp);
    	vis[tmp]--;
    }

}
int main()
{
	pre(1e6);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

C.Strange Shuffle
给定一个序列,初始都为k,每次询问后,每个数会向其前一个给x/2向下取整,向后一个给x/2向上取整,其中有一个特殊的位置p,其只会将所有的x丢给后一个数,现在可以询问1000次,每次可以询问某一个位置的值,要求找到这个p位置。

首先可以稍微模拟一下,发现p的两端受其影响的数的数量是操作数,其左边都是小于他的,其右边都是大于他的。那么只要找到一个与k不相等的位置,然后就可以得到p的区间然后二分查找即可。那么现在问题就是如果在一定次数内找到与k不相等的数。考虑每次询问后,所受到的区间影响序列为[3,5,7,9,11,……],然后为了不重复访问某些位置,将这些长度不相交地放到序列中,这样实测只需要300多次可以将序列访问完,如果找的所有点都是k,那么再按当前放入的最长长度继续查询,只需要200不到次。如果还是没有查到,那么只会有我们当前点是p或者p的对面,当n为偶数时,无论多少次,p的对面是k。那么考虑当前点的左边是否小于k,然后就可以判断当前点是p还是p的对面。
oh,我是菜鸡,前面瞎跑,将长度扩大到一定后,跑后面那个就可以了,类似于根号做法。
emmmm,好像直接rand找也可以(555555555)。

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
int n,k;
int qy(int x)
{
	printf("? %d\n",x);
	fflush(stdout);
	int y;
	scanf("%d",&y);
	return y;
}
void find(int x,int y)
{
	int l=x,r=y;
	while(l<=r){
		int m=(l+r)>>1;
		int cnt=qy((m+10*n-1)%n+1);
		if(cnt<k){
			l=m+1;
		}else if(cnt>k){
			r=m-1;
		}else{
			printf("! %d\n",(m+10*n-1)%n+1);
			return;
		}
	}
}
void work()
{
    scanf("%d%d",&n,&k);
    qy(1);
    int cnt=2;
    for(int i=1;i<=n;i+=cnt){
    	int now=qy(i);
    	if(now<k){
    		find(i,i+(cnt)/2);return;
    	}else if(now>k){
    		find(i-(cnt)/2,i);return;
    	}
    	cnt+=2;
    }
    int ans=2;
    int cnt1=cnt;
    for(int i=2;i<=n;i+=cnt1){
    	int now=qy(i);
    	if(now<k){
    		find(i,i+(cnt)/2);return;
    	}else if(now>k){
    		find(i-(cnt)/2,i);return;
    	}
    	cnt+=2;
    	cnt=min(cnt,n+1);
    }
    if(qy(ans-1)<=k&&qy(ans-1)<=k){
    	printf("! %d\n",ans);
    }else{
    	ans=(ans+n/2-1)%n+1;
    	printf("! %d\n",ans);
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

D.Strange Housing
给定一张图,要在图中选定一些点,若一条边的两端都没有被选到,这条边会被删掉,要求最后不存在一条边两端都被选到,并且所有点互通。
一开始想到了一般图最大独立集,然后发现并没有要求数量,所以直接dfs染色即可,需要判断一下图是否连通。(为什么这么简单的题会出在div1D,最后十分钟写还少了清空)

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=3e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
vector<int>v[N];
int vis[N];
int fa[N];
int ans[N];
int find(int x)
{
	if(fa[x]!=x)return fa[x]=find(fa[x]);
	return x;
}
void uni(int x,int y)
{
	x=find(x);
	y=find(y);
	if(x!=y){
		fa[x]=y;
	}
}
void dfs(int x)
{
	vis[x]=1;
	bool f=1;
	for(auto y:v[x]){
		if(ans[y]){
			f=0;break;
		}
	}
	if(f){
		ans[x]=1;
	}
	for(auto y:v[x]){
		if(!vis[y]){
			dfs(y);
		}
	}
}
void work()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
    	v[i].clear();
    	vis[i]=0;
    	fa[i]=i;
    	ans[i]=0;
    }
    for(int i=1;i<=m;i++){
    	int x,y;
    	scanf("%d%d",&x,&y);
    	v[x].push_back(y);
    	v[y].push_back(x);
    	uni(x,y);
    }
    for(int i=2;i<=n;i++){
    	if(find(i)!=find(i-1)){
    		printf("NO\n");return;
    	}
    }
    dfs(1);
    int sum=0;
    for(int i=1;i<=n;i++){
    	if(ans[i])sum++;
    }
    printf("YES\n");
    printf("%d\n",sum);
    for(int i=1;i<=n;i++){
    	if(ans[i]){
    		printf("%d ",i);
    	}
    }
    printf("\n");
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注