Fork me on GitHub

「Codeforces」CF-Round485 Div2 复盘

发表于 | 分类于
字数统计: 3,022字 | 阅读时长 ≈ 17分钟

我这种傻逼选手也只能做做Div2练练手了…

链接

CF-Round485 Div2

某彩笔选手的Room

Ranklist

算是CF打到现在自己发挥算好的吧..但是为什么才涨了49分啊…不资瓷啊.

以后每次比赛都写一次复盘吧.（有可能我懒不想写

划水记

赛前

半夜23:35开打的Div2,肝快爆了,ZhangZisu还有GCC314大爷带我飞啊啊啊啊啊.

赛前疯狂打CodeSource(滑稽

尝试着睡着但是没成功,魔爪也没啦,抱着必掉$rating$的心打的比赛.

赛中

A

一看哇特么的是 复联3 灭霸1背景诶!傻逼题,手速还是慢啊花了6min.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
//my vegetable has exploded. :(
#include<bits/stdc++.h>
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define MM(x,y) memset(x,y,sizeof(x))
#define MCPY(a,b) memcpy(a,b,sizeof(b))
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=b;i>=a;i--)
#define fi first
#define se second
#define int long long
using namespace std;

inline int quickpow(int m,int n,int p){int b=1;while(n){if(n&1)b=b*m%p;n=n>>1;m=m*m%p;}return b;}
inline int getinv(int x,int p){return quickpow(x,p-2,p);}
inline int read(void){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){f=ch=='-'?-1:1;ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return x * f;
}
int write(int x){
	if(x<0) putchar('-'); x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
}

string s[7] = {"Reality","Power","Mind","Soul","Space","Time"};
string wd[7] = {"red","purple","yellow","orange","blue","green"};
bool g[7];

///------------------head------------------
signed main(signed argc, char *argv[]){
	MM(g,0);
	int n=read(),ans=0;
	while(n--){
		string s;
		cin >> s;
		rep(i,0,5) if (wd[i] == s) g[i] = 1;
	}
	rep(i,0,5) ans += (!g[i]);
	cout << ans << endl;
	rep(i,0,5) if(!g[i]) cout << s[i] << endl; 
	return 0;
}

B.

给出$x$,$y$,求比较$x^y,y^x$的大小.

log一下什么的就好了.愚蠢的我忘了换底公式.

只能pow了.我菜爆了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
//my vegetable has exploded. :(
#include<bits/stdc++.h>
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define MM(x,y) memset(x,y,sizeof(x))
#define MCPY(a,b) memcpy(a,b,sizeof(b))
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=b;i>=a;i--)
#define fi first
#define se second
#define int long long
using namespace std;
const double eps = 1e-8;
inline int quickpow(int m,int n,int p){int b=1;while(n){if(n&1)b=b*m%p;n=n>>1;m=m*m%p;}return b;}
inline int getinv(int x,int p){return quickpow(x,p-2,p);}
inline int read(void){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){f=ch=='-'?-1:1;ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return x * f;
}
int write(int x){
	if(x<0) putchar('-'); x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
}
double x,y,r;
///------------------head------------------
signed main(signed argc, char *argv[]){
	cin >> x >> y;
	if (x == 2 && y == 4){puts("="); return 0;}
	if (x == 4 && y == 2){puts("="); return 0;}
	if (x < y){
		double a1 = x,a2 = pow(y,x/y);
		printf("%c\n",(a1-a2 > eps) ? '>' : '<');
	}
	else if (x == y) {puts("=");}
	else {
		double a1 = x,a2 = pow(y,x/y);
		printf("%c\n",(a1-a2 > eps) ? '>' : '<');
	}
	return 0;
}

C.

给定$n,{ s_i} {c_i},1 \leq n \leq 3000$,求三元组$(i,j,k)$满足$s_i < s_j < s_k,i<j<k$

求出最小的$c_i+c_j+c_k$

似乎是个DP啊,想了好久的奇怪做法(二分+RMQ)

然后发现是个$O(n^2)$的DP

啊啊啊啊啊

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
//my vegetable has exploded. :(
#include<bits/stdc++.h>
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define MM(x,y) memset(x,y,sizeof(x))
#define MCPY(a,b) memcpy(a,b,sizeof(b))
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=b;i>=a;i--)
#define fi first
#define se second
#define INF 1000000000000001LL
using namespace std;
const int maxn = 3003;

inline int quickpow(int m,int n,int p){int b=1;while(n){if(n&1)b=b*m%p;n=n>>1;m=m*m%p;}return b;}
inline int getinv(int x,int p){return quickpow(x,p-2,p);}
inline int read(void){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){f=ch=='-'?-1:1;ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return x * f;
}
int write(int x){
	if(x<0) putchar('-'); x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
}
int n,a[maxn],b[maxn],f[maxn][4];
int d[maxn][100];
void RMQ_init(int a[],int n)
{
	for (int i = 1; i <= n; i++)
	d[i][0] = a[i];
	for (int j = 1; (1<<j) <= n; j++)
		for (int i = 0; i + (1<<j) - 1 <= n; i++) //可以从第0位置开始
		d[i][j] = min(d[i][j-1],d[i+(1<<(j-1))][j-1]);
} 
int RMQ_query(int l,int r)
{
	int k = 0;
	while((1<<(k+1)) <= r-l+1) k++;
	return min(d[l][k],d[r-(1<<k)+1][k]);
}
///------------------head------------------
signed main(signed argc, char *argv[]){
	n=read();
	int ans = 0x3F3F3F3F;
	for (int i=1;i<=n;i++)a[i]=read();
	for (int i=1;i<=n;i++)b[i]=read();
	a[0]=0x80000000;
	memset(f,0x3F,sizeof(f));
	f[0][0] = 0;
	rep(i,1,n)
		rep(j,1,3)
			rep(k,0,i-1)
			{
				if(a[k] >= a[i]) continue;
				f[i][j] = min(f[i][j],f[k][j-1]+b[i]);
			}
	rep(i,1,n) ans=min(ans,f[i][3]);
	printf("%d\n",ans>300000001?-1:ans);
	return 0;
}

D.

题意:

有$n$个村庄,$m$条边,每条边默认的边权为1,每个村庄有一个货物$x_i$,货物最多有$min(100,k)$种

分别求每个村庄作为主办方(要从其他村庄获取货物),要展览$s$个物品的最小花费？

(每种货物算1个)

思考了很久很久啊..中间一会儿看E一会儿看D并行地写啊..

发现是个傻逼题.

对于每种货物.选取当前的货物种类$x$,扔到队列里笨法师一遍,记录$F(i,x)$,表示第x种货物搬到村庄$i$的最小花费.这样是$O(nk)$的,那么每次每个村庄在$F(i)$里的$x$,$sort$一下求前$s$个就完事了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
//my vegetable has exploded. :(
#include<bits/stdc++.h>
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define MM(x,y) memset(x,y,sizeof(x))
#define MCPY(a,b) memcpy(a,b,sizeof(b))
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=b;i>=a;i--)
#define fi first
#define se second
#define int long long
using namespace std;

inline int quickpow(int m,int n,int p){int b=1;while(n){if(n&1)b=b*m%p;n=n>>1;m=m*m%p;}return b;}
inline int getinv(int x,int p){return quickpow(x,p-2,p);}
inline int read(void){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){f=ch=='-'?-1:1;ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return x * f;
}
int write(int x){
	if(x<0) putchar('-'); x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
}
const int maxn = 1e5+10;
int n,m,s,k;
bool vis[maxn];
int f[maxn][101];
int b[101],ans;
int types[100010];
queue<pair<int,int> >q;
pair<int,int> pa; 
vector<int>lt[maxn];
///------------------head------------------
signed main(signed argc, char *argv[]){
	MM(f,0x7f);
	n=read(),m=read(),k=read(),s=read();
	rep(i,1,n) types[i]=read();
	rep(i,1,m) {
		int x=read(),y=read();
		lt[x].push_back(y);
		lt[y].push_back(x); 
	}
	//system("pause");
	for (int i = 1; i <= min(100,k); i++){
		MM(vis,0);
		while(!q.empty())q.pop();
		for (int j=1;j<=n;j++)
		if(i==types[j])vis[j]=1,q.push(make_pair(j,0));
		while(!q.empty())
		{
			pa = q.front();
			q.pop();
			f[pa.fi][i] = min(f[pa.fi][i],pa.se);
			for(int oo = 0; oo < lt[pa.fi].size(); oo++)
				if(!vis[lt[pa.fi][oo]]) vis[lt[pa.fi][oo]]=1,q.push(make_pair(lt[pa.fi][oo],pa.se+1));
		}
	} 
	for (int i = 1; i <= n; i++){
		ans=0;
		memcpy(b,f[i],sizeof(f[i]));
		sort(b+1,b+100+1);
		for(int p=1;p<=s;p++) ans+=b[p];
		cout << ans << " ";
	}
	return 0;
}

E.

给一个1~N的排列,Petr把两个不同元素交换$3n$次得到一个新的序列,Um_nik把两个不同元素交换$7n+1$次得到一个新的序列.现在给出这个新的序列,求是谁操作了这个序列.

求逆序对就完事了.01:49想到的做法,1发入魂.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
//my vegetable has exploded. :(
#include<bits/stdc++.h>
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define MM(x,y) memset(x,y,sizeof(x))
#define MCPY(a,b) memcpy(a,b,sizeof(b))
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=b;i>=a;i--)
#define fi first
#define se second
#define int long long
using namespace std;
const int maxn = 1e6+10;

inline int quickpow(int m,int n,int p){int b=1;while(n){if(n&1)b=b*m%p;n=n>>1;m=m*m%p;}return b;}
inline int getinv(int x,int p){return quickpow(x,p-2,p);}
inline int read(void){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){f=ch=='-'?-1:1;ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return x * f;
}
int write(int x){
	if(x<0) putchar('-'); x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
}
int b[maxn],n;
namespace getrev{
	int a[maxn],c[maxn],ans=0;
	void x(int l,int r){
		int mid=(l+r)/2,i,j,tmp;   
   		if(r>l)   
	    {   
	        x(l,mid);   
	        x(mid+1,r);   
	        tmp=l;   
	        for(i=l,j=mid+1;i<=mid&&j<=r;)   
	        {   
	            if(a[i]>a[j])   
	            {   
	                c[tmp++]=a[j++];   
	                ans+=mid-i+1;   
	            }   
	            else c[tmp++]=a[i++];   
	        }   
	        if(i<=mid) for(;i<=mid;) c[tmp++]=a[i++];   
	        if(j<=r) for(;j<=r;) c[tmp++]=a[j++];   
	        for(i=l;i<=r;i++) a[i]=c[i];  
		}
	}
	int sol(void){
		memcpy(a,b,sizeof(b));
		x(1,n); 
		return ans;
	}
}
///------------------head------------------
signed main(signed argc, char *argv[]){
	n=read();
	rep(i,1,n) b[i]=read();
	int petr=(n*3) & 1;
	int cnt=getrev::sol();
	cnt=cnt&1;
	printf("%s\n",cnt==petr?"Petr":"Um_nik");
	return 0;
}

F.(订正)

给出n,给出m个$1\leq x \leq 2^n$的元素,其中某两个元素$a,b$有连边当且仅当$a \&b = 0$

求联通快的个数.

看上去很不可做！

ckr:我几秒钟就秒掉了

被D爆了啊…

首先$3^n$的暴力是很显然的,但是通不过,考虑优化.

ckr:”我们尝试着Gay掉1位”

类似于记忆化的过程,我们在dfs时记录vis[x]表示访问过x.

我们在dfs时枚举$0-n$,如果$(2^i \& x)$,就可以Gay掉.

继续下去$dfs(x^{2^i})$

如果x在读入种出现了就dfs它的补集.

因为x的补集种所有子集必然与x联通,因此正确性显然.

哇 我特么这都没想到.是被难度吓退了啊.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
//my vegetable has exploded. :(
#include<bits/stdc++.h>
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define MM(x,y) memset(x,y,sizeof(x))
#define MCPY(a,b) memcpy(a,b,sizeof(b))
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=b;i>=a;i--)
#define fi first
#define se second
#define int long long
using namespace std;

inline int quickpow(int m,int n,int p){int b=1;while(n){if(n&1)b=b*m%p;n=n>>1;m=m*m%p;}return b;}
inline int getinv(int x,int p){return quickpow(x,p-2,p);}
inline int read(void){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){f=ch=='-'?-1:1;ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return x * f;
}
int write(int x){
	if(x<0) putchar('-'); x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
}

const int N = 1<<23;
int vis[N],ins[N],ans=0,x,n,m;
void dfs(int u){
	if(vis[u]) return ;vis[u]=1;
	rep(i,0,n-1)
		if((1<<i)&u) dfs((1<<i)^u);
	if(ins[u]) dfs((1<<n)-1-u);
}
///------------------head------------------
signed main(signed argc, char *argv[]){
	MM(ins,0);
	n=read(),m=read();
	while(m--){
		x=read();
		ins[x]=1;
	}
	if(n==1&&ins[1]) return puts("1"),0;
	rep(i,0,(1<<n)-1){
		if(!(vis[i]||!ins[i])){
			++ans;
			dfs((1<<n)-i-1);
		}
	}
	printf("%d\n",ans);
	return 0;
}

后记

算是第一次打到5题吧..

之后要坚持啊…

​ karriganasta :P