18

【Codeforces 1475】Codeforces Round #697 (Div. 3) | 全题解

 3 years ago
source link: https://blog.csdn.net/qq_43857314/article/details/113158367
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

：比赛连接

emm，消极了，消极了。这场可以 a k ak ak的，看到 u n r unr unr不想打了，奇怪了，本身我也不加分的呀。

赛后 3 3 3分钟过 G G G， 10 10 10分钟过 F F F，不该消极的。

不传播负能量了，开始题解了。

A.Odd Divisor

题目大意：

判断一个整数 n n n，是否具有为奇数的因子

题目思路：

水题了吧.

只需要判断是否是2的幂即可，不是2的幂必定有奇数因子呀。

Code:

/*** keep hungry and calm CoolGuang!  ***/
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e18+7;
const ll maxn = 1e6+700;
const ll mod= 1000000007;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
int main(){
	int T;scanf("%d",&T);
	while(T--){
		read(n);
		while(n!=1){
			if(n%2 == 0) n/=2;
			else break;
		}
		printf("%s\n",n==1?"NO":"YES");
	}
 	return 0;

}
/***
7
6 6 2 7 4 2 5
7
1 3 6
2 1 2 2
***/

B.New Year’s Number

题目大意：

判断一个整数 n n n，是否可以有若干个 2020 2020 2020和若干个 2021 2021 2021组成

题目思路：

令 x = n / 2020 x = n/2020 x=n/2020:

  • x = = 0 x == 0 x==0 : N O NO NO
  • n % 2020 < = x n\%2020 <= x n%2020<=x : Y E S YES YES

Code：

/*** keep hungry and calm CoolGuang!  ***/
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e18+7;
const ll maxn = 1e6+700;
const ll mod= 1000000007;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
int main(){
	int T;scanf("%d",&T);
	while(T--){
		read(n);
		ll temp = n/2020;
		if(temp <= 0) printf("NO\n");
		else{
			if(n%2020 <= temp) printf("YES\n");
			else printf("NO\n");
		}
	}
 	return 0;

}
/***
7
6 6 2 7 4 2 5
7
1 3 6
2 1 2 2
***/

C.Ball in Berland

题目大意：

其实这题目，我没读完，猜的题意。

询问有多少对 ( a , b ) , ( c , d ) (a,b),(c,d) (a,b),(c,d)使得 a ! = c , b ! = d a != c,b != d a!=c,b!=d

题目思路：

显然的容斥原理：

假设 i i i可以与前面的 ( i − 1 ) (i-1) (i−1)都组合，然后减去不符合要求的。

令 A A A集合代表男生在同一集合， B B B代表女生在同一集合，显然求： A ∪ B A∪B A∪B

m a p map map存一下，直接容斥原理就好了。

Code:

/*** keep hungry and calm CoolGuang!  ***/
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e18+7;
const ll maxn = 1e6+700;
const ll mod= 1000000007;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
map<int,int>A,B;
map<pair<int,int>,int>C;
ll a[maxn],b[maxn];
int main(){
	int T;scanf("%d",&T);
	while(T--){
		ll att,bt;
		read(att);read(bt);read(n);
		A.clear();B.clear();C.clear();
		for(int i=1;i<=n;i++) read(a[i]);
		for(int i=1;i<=n;i++) read(b[i]);
		ll ans = 0;
		for(int i=1;i<=n;i++){	
			

			ans += (i-1)*1ll - (A[a[i]]+B[b[i]]-C[{a[i],b[i]}]);
			A[a[i]]++;B[b[i]]++;
			C[{a[i],b[i]}]++;
			//debug(ans);
		}
		dl(ans);
	}
 	return 0;

}
/***
7
6 6 2 7 4 2 5
7
1 3 6
2 1 2 2
***/

D. Cleaning the Phone

题目大意：

抽象：给出 N N N个物品，每个物品有一个质量和花费，求出在质量大于等于 m m m时的最小花费。

题目思路：

其实这个题卡了略久(这场的原因都在这了)

看错题意没有发现 b i b_i bi​只有两种取值，因为只有两种取值，所以可以直接枚举最终状态，即：取第一种取值的 b i b_i bi​在最终答案中可能有多少个,之后按照贪心去计算最小花费。尺取二分都可，这里采用的二分。

Code:

/*** keep hungry and calm CoolGuang!  ***/
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e18+7;
const ll maxn = 1e6+700;
const ll mod= 1000000007;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
struct node{
	ll x,y;
	bool friend operator<(node a,node b){
		if(a.y == b.y) return a.x > b.x;
		return a.y < b.y;
	}
}q[maxn];
ll sum[maxn];
int main(){
	int T;scanf("%d",&T);
	while(T--){
		read(n);read(m);
		for(int i=1;i<=n;i++) read(q[i].x);
		for(int i=1;i<=n;i++) read(q[i].y);
		sort(q+1,q+1+n);
		int last = 0;
		for(int i=1;i<=n;i++){
			if(q[i].y == 1) last = i;
			sum[i] = sum[i-1] + q[i].x;
		}
		if(sum[n]<m){
			printf("-1\n");
			continue;
		}
		ll ans = INF;
		for(int i=0;i<=last;i++){
			int l = last,r = n;
			int tmp = -1;
			while(l<=r){
				int mid = (l+r)/2;
				if(sum[mid]-sum[last] + sum[i] >= m){
					r = mid-1;
					tmp = mid;
				}else l = mid+1;
			}
			if(tmp!=-1) ans = min(ans,i*1 + (tmp-last)*2ll);
		}
		printf("%lld\n",ans);
	}
 	return 0;

}
/***
7
6 6 2 7 4 2 5
7
1 3 6
2 1 2 2
***/

E. Advertising Agency

题目大意:

首先令 m x = mx = mx=数组的长度为k的最大子序列和。

询问有多少个长度为 k k k的子序列的和 = m x = mx =mx

题目思路：

这题估计挺多做法的

令 d p i j dp_{ij} dpij​代表以第i个数字结尾，长度为j的子序列的最大和。
令 c i j c_{ij} cij​代表以第i个数字结尾，长度为j的子序列的最大和的数量。

首先类比最短路计数的状态转移得到：

  • d p [ i ] [ j ] < d p [ k ] [ j − 1 ] + a [ i ] − > d p [ i ] [ j ] = d p [ k ] [ j − 1 ] + a [ i ] , c [ i ] [ j ] = c [ k ] [ j − 1 ] dp[i][j] < dp[k][j-1]+a[i] -> dp[i][j] = dp[k][j-1]+a[i],c[i][j] = c[k][j-1] dp[i][j]<dp[k][j−1]+a[i]−>dp[i][j]=dp[k][j−1]+a[i],c[i][j]=c[k][j−1]
  • d p [ i ] [ j ] = d p [ k ] [ j − 1 ] + a [ i ] − > c [ i ] [ j ] = c [ i ] [ j ] + c [ k ] [ j − 1 ] dp[i][j] = dp[k][j-1]+a[i] -> c[i][j] = c[i][j] + c[k][j-1] dp[i][j]=dp[k][j−1]+a[i]−>c[i][j]=c[i][j]+c[k][j−1]
  • 1 ≤ k < i 1 \le k \lt i 1≤k<i

显然是个三维循环，但是与最大值有关系，所以用前缀最大值，和前缀最大值的数量优化掉一层 f o r for for即可

Code:

/*** keep hungry and calm CoolGuang!  ***/
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e18+7;
const ll maxn = 1e6+700;
const ll mod= 1000000007;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
ll dp[1005][1005],c[1005][1005];
ll pre[1005],ct[1005];
ll a[maxn];
int main(){
	int T;scanf("%d",&T);
	while(T--){
		read(n);read(m);
		for(int i=1;i<=n;i++) read(a[i]);

		memset(ct,0,sizeof(ct));
		memset(pre,0,sizeof(pre));
		for(int i=0;i<=n;i++)
			for(int k=0;k<=m;k++)
				dp[i][k] = c[i][k] = 0;
		c[0][0] = 1;
		ct[0] = 1;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(dp[i][j]<pre[j-1]+a[i]){
					dp[i][j] = pre[j-1]+a[i];
					c[i][j] = ct[j-1];
				}else if(dp[i][j] == pre[j-1]+a[i]) c[i][j] = (c[i][j] + ct[j-1])%mod;
			}
			for(int j=0;j<=m;j++){
				if(pre[j]<dp[i][j]){
					ct[j] = c[i][j];
					pre[j] = dp[i][j];
				}else if(pre[j] == dp[i][j]) ct[j] = (ct[j] + c[i][j])%mod;
			}
		}
		ll ans = 0,mx = 0;
		for(int i=1;i<=n;i++) mx = max(mx,dp[i][m]);
		//debug(mx);
		for(int i=1;i<=n;i++) 
			if(mx == dp[i][m])
				ans = (ans + c[i][m])%mod; 
		dl(ans);
	}
 	return 0;

}
/***
7
6 6 2 7 4 2 5
7
1 3 6
2 1 2 2
***/

F. Unusual Matrix

题目大意：

给出两个 01 01 01矩阵， s s s与 t t t。每次可以将 s s s的一行进行异或，或者将 t t t的一行进行异或，询问是否可以通过一系列的操作使得 s s s变成 t t t。

题目思路：

一个思维题。

可以考虑对 ( i , j ) (i,j) (i,j)操作的关联性，对 ( i , j ) (i,j) (i,j)操作就会改变 ( 1 , j ) (1,j) (1,j)或者 ( i , 1 ) (i,1) (i,1)的值，但是这两个还可以通过 ( 1 , 1 ) (1,1) (1,1)再改变回来。所以这四个就是一个关联组。当全一样或者全不一样的时候就不可以使得四个都满足。

Code：

/*** keep hungry and calm CoolGuang!  ***/
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e18+7;
const ll maxn = 1e6+700;
const ll mod= 1000000007;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
char s[maxn];
int c[1005][1005];
int main(){
	int T;scanf("%d",&T);
	while(T--){
		read(n);
		for(int i=1;i<=n;i++){
			scanf("%s",s+1);
			for(int k=1;k<=n;k++) c[i][k] = s[k]-'0';
		}
		for(int i=1;i<=n;i++){
			scanf("%s",s+1);
			for(int k=1;k<=n;k++) c[i][k] ^= s[k]-'0';
		}
		int flag = 0;
		for(int i=2;i<=n;i++){
			for(int k=2;k<=n;k++){
				if(c[1][k]^c[i][1]^c[1][1]^c[i][k]) flag = 1; 
			}
		}
		printf("%s\n",flag?"NO":"YES");
	}
 	return 0;

}
/***
7
6 6 2 7 4 2 5
7
1 3 6
2 1 2 2
***/

G. Strange Beauty

题目大意：

定义一个数组是好的，当前仅当任意两个数 i , j i,j i,j都满足 a i ∣ a j a_i | a_j ai​∣aj​ 或者 a j ∣ a i a_j | a_i aj​∣ai​。

问最少删除几个数使得数组变好。

题目思路：

考虑从小到大将数组排序(其实并不用,方便理解)

令 d p i dp_i dpi​代表最大值是 a i a_i ai​好的数组的最大容量是多少

那么很显然:

i f ( a k % a i = = 0 ) if(a_k\%a_i==0) if(ak​%ai​==0) d p [ i ] = d p [ k ] + a i dp[i] = dp[k] + a_i dp[i]=dp[k]+ai​的数量

R e a s o n : Reason: Reason:最大值是 a k a_k ak​， a i a_i ai​肯定也整除 a k a_k ak​整除的数

所以只需要知道有哪些因子即可 —— 筛法筛一筛？

Code：

/*** keep hungry and calm CoolGuang!  ***/
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e18+7;
const ll maxn = 1e6+700;
const ll mod= 1000000007;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
ll a[maxn];
ll vis[maxn];
ll c[maxn],w[maxn];
ll dp[maxn];
vector<int>v[maxn];
int main(){
	int T;scanf("%d",&T);
	while(T--){
		read(n);
		ll mx = 0;
		for(int i=1;i<=n;i++){
			read(a[i]);
			mx = max(mx,a[i]);
			vis[a[i]]++;
		}
		for(int i=1;i<=mx;i++){
			v[i].clear();
			dp[i] = 0;
		}
		ll ans = INF;
		for(int i=1;i<=mx;i++){
			for(int k=2*i;k<=mx;k+=i)  v[k].push_back(i);
		}
		sort(a+1,a+1+n);
		//for(int i=1;i<=n;i++) printf("%lld ",a[i]);
		for(int i=1;i<=n;i++){
			dp[a[i]] = vis[a[i]];
		
			for(int e:v[a[i]]) dp[a[i]] = max(dp[e]+vis[a[i]],dp[a[i]]);
			//debug(dp[a[i]]);
			int k = i;
			ans = min(ans,n-dp[a[i]]);
			while(a[k] == a[i] && k<=n) k++;
			i = k-1;

		}
		printf("%lld\n",ans);
		for(int i=1;i<=n;i++) vis[a[i]]--;
	}
 	return 0;

}
/***
7
6 6 2 7 4 2 5
7
1 3 6
2 1 2 2
***/

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK