可能是最后一场CF题解

发表于 | 评论数： | 阅读次数：

A - Minimum Integer(签到)

想清楚我直接累加会超时,我们就判断一下如果不在其中就直接输出否则就用右边的r的下一个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	ll t;
	cin>>t;
	while(t--)
	{
		ll x,y,z;
		cin>>x>>y>>z;
		if(z<x||z>y)
		cout<<z<<"\n";
		else
		cout<<((y/z)+1)*z<<"\n";
	}
}

B - Accordion(模拟)

就是我们先找到最左边和最右边的[]然后再找到::最后从::中找|

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	int ans=0,st,ed,f=0;
	string x;
	cin>>x;
	for(int i=0;i<x.size();i++)
	if(x[i]=='[')
	{
		st=i,f=1;
		break;
	}
	if(!f)
	return cout<<-1,0;
	f=0;
	for(int i=x.size()-1;i>st;i--)
	if(x[i]==']')
	{
		ed=i,f=1;
		break;
	}
	if(!f)
	return cout<<-1,0;
	f=0;
	for(int i=st;i<ed;i++)
	if(x[i]==':')
	{
		st=i,f=1;
		break;
	}
	if(!f)
	return cout<<-1,0;
	f=0;
	for(int i=ed;i>st;i--)
	if(x[i]==':')
	{
		ed=i,f=1;
		break;
	}
	if(!f)
	return cout<<-1,0;
	f=0;
	for(int i=st;i<=ed;i++)
	if(x[i]=='|')
	ans++;
	cout<<ans+4;
}

C - Strings Equalization(思维)

直接判断如果两个字符串有相同的字符那么就可以转换否则不能

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll bk1[305],bk2[305];
int main()
{
	ios::sync_with_stdio(0);
	ll t;
	cin>>t;
	while(t--)
	{
		string a,b;
		int f=0;
		cin>>a>>b;
		memset(bk1,0,sizeof(bk1));
		memset(bk2,0,sizeof(bk2));
		for(int i=0;i<a.size();i++)
		{
			bk1[a[i]]++,bk2[b[i]]++;
		}
		for(int i='a';i<='z';i++)
		if(bk1[i]&&bk2[i])
		{
			f=1;
			break;
		}
		if(f)
		puts("YES");
		else
		puts("NO");
	}
}

D - Knights(思维or构造)

思维就是WBWBWB这样的
构造的话就是一个一个放进去即可 

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
71
72
73
74
75
76
77
78
79
80
81
82
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[105][105],bk[105][105],n;
int check(int x,int y)
{
	if(x>=1&&x<=n&&y>=1&&y<=n)
	return 1;
	else
	return 0;
}
void dye(int x,int y)
{
	if(!check(x,y))
	return;
	if(check(x-2,y-1)&&!bk[x-2][y-1])
	{
		bk[x-2][y-1]=1;
		a[x-2][y-1]=!a[x][y];
		dye(x-2,y-1);
	}
	if(check(x-2,y+1)&&!bk[x-2][y+1])
	{
		bk[x-2][y+1]=1;
		a[x-2][y+1]=!a[x][y];
		dye(x-2,y+1);
	}
	if(check(x-1,y-2)&&!bk[x-1][y-2])
	{
		bk[x-1][y-2]=1;
		a[x-1][y-2]=!a[x][y];
		dye(x-1,y-2);
	}
	if(check(x-1,y+2)&&!bk[x-1][y+2])
	{
		bk[x-1][y+2]=1;
		a[x-1][y+2]=!a[x][y];
		dye(x-1,y+2);
	}
	if(check(x+2,y-1)&&!bk[x+2][y-1])
	{
		bk[x+2][y-1]=1;
		a[x+2][y-1]=!a[x][y];
		dye(x+2,y-1);
	}
	if(check(x+2,y+1)&&!bk[x+2][y+1])
	{
		bk[x+2][y+1]=1;
		a[x+2][y+1]=!a[x][y];
		dye(x+2,y+1);
	}
	if(check(x+1,y-2)&&!bk[x+1][y-2])
	{
		bk[x+1][y-2]=1;
		a[x+1][y-2]=!a[x][y];
		dye(x+1,y-2);
	}
	if(check(x+1,y+2)&&!bk[x+1][y+2])
	{
		bk[x+1][y+2]=1;
		a[x+1][y+2]=!a[x][y];
		dye(x+1,y+2);
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	if(!bk[i][j])
	{
		bk[i][j]=1;
		a[i][j]=1;
		dye(i,j);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		printf("%c",a[i][j]?'W':'B');
		printf("\n");
	}
}

或者直接思维即可 by dhz

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;

char s[1000], t[1000];
int main()
{
    int temp;
    cin >> temp;
    while (temp--) {
        cin >> s >> t;
        int len = strlen(s), flag = 0;
        for (int i = 0; i < len; i++)
            for (int j = 0; j < len; j++)
                if (s[i] == t[j]) {
                    flag = 1;
                    break;
                }
        cout << (flag ? "YES" : "NO") << endl;
    }
}

E - Pipes(思维)

我也没有啥的好方法，我就把每种可能进去的情况都想了一下然后走一下，可以发现就两行也走不了多少，直接递归走能走出来就ok了

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
71
72
73
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f,n,a[5][300005];
void go(int x,int y,int px,int py)
{
//	cout<<x<<" "<<y<<"\n";
	if(x>2||y>n||x==0||y==0)
	return;
	if(x==2&&y==n)
	{
		if(a[x][y]>=1&&a[x][y]<=2)
		{
			if(px==2&&py==n-1)
			f=1;
		}
		else
		{
			if(px==1&&py==n)
			f=1;
		}
		return;
	}
	if(a[x][y]>=1&&a[x][y]<=2)
	go(x,y+1,x,y);
	else
	{
		if(x==1)
		{
			if(px==1)
			{
				if(a[x+1][y]>2)
				go(x+1,y,x,y);
			}
			else
			go(x,y+1,x,y);
		}
		else
		{
			if(px==1)
			go(x,y+1,x,y);
			else
			{
				if(a[x-1][y]>2)
				go(x-1,y,x,y);
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(0);
	ll t;
	cin>>t;
	while(t--)
	{
		cin>>n;
		for(int i=1;i<=2;i++)
		for(int j=1;j<=n;j++)
		{
			char x;
			cin>>x;
			a[i][j]=x-'0';
		}
		f=0;
		go(1,1,1,1);
		if(f)
		cout<<"YES\n";
		else
		cout<<"NO\n";
	}

}

F - Save the Nature(二分)

二分裸题啊，nlog^2n 二分里面排序贪心

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200005;
struct node
{
	ll id,v;
}jk[N],re[N];
ll f,lcmm,a,b;
ll aa[N],maxn,minn,mk[N],k,bk[N],mkk[N];
bool cmp1(node a,node b)
{
	return a.v>b.v;
}
ll check(ll x)
{
	double sum=0;
	for(int i=1;i<=x;i++)
	re[i]=jk[i];
	sort(re+1,re+1+x,cmp1);
	for(int i=1;i<=x;i++)
	sum+=aa[i]*re[i].v;
	return sum>=k*100LL;
}
bool cmp(ll a,ll b)
{
	return a>b;
}
int main()
{
	ios::sync_with_stdio(0);
	ll t;
	cin>>t;
	while(t--)
	{
		ll n,p=0;
		cin>>n;
		for(int i=1;i<=n;i++)
		cin>>aa[i];
		for(int i=1;i<=n;i++)
		mk[i]=0;
		double x,y;
		cin>>x>>a>>y>>b>>k;
		for(int i=a;i<=n;i+=a)
		mk[i]+=x;
		for(int i=b;i<=n;i+=b)
		mk[i]+=y;
		for(int i=1;i<=n;i++)
		if(mk[i]>0)
		jk[++p]=(node){i,mk[i]};
		sort(aa+1,aa+1+n,cmp);
		ll l=1,r=p;
		while(r-l>1)
		{
			ll mid=(l+r)>>1;
			//cout<<mid<<"\n";
			if(check(mid))
			r=mid;
			else
			l=mid;
		}
		if(check(l))
		cout<<jk[l].id<<"\n";
		else if(check(r))
		cout<<jk[r].id<<"\n";
		else
		cout<<"-1\n";
	}
}

G - Anadi and Domino(N^N暴力)

直接搜索暴力枚举7个点都是几我们两个点是多少知道了那么我们筛子边也就知道了，对于图我们判断一下是否符合然后求个极值

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
#include <bits/stdc++.h>
using namespace std;
int mk[105][105],dye[105],n,m,ans,x,y,mp[105][105],mpp[105][105],bk[105][105];
void dfs(int cur)
{
	if(cur==n+1)
	{
		int jk=0;
//		for(int i=1;i<=n;i++)
//		cout<<dye[i]<<" ";
//		cout<<"\n";
		for(int i=1;i<=6;i++)
		for(int j=1;j<=6;j++)
		mk[i][j]=0;
		for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		mpp[i][j]=mp[i][j];
		for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		if(mpp[i][j]||mpp[j][i])
		if(!mk[dye[i]][dye[j]]&&dye[i]<=dye[j])
		{
			mk[dye[i]][dye[j]]=1;
			mpp[i][j]=mpp[j][i]=0;
			jk++;
		}
		ans=max(ans,jk);
	}
	else
	{
		for(int i=cur;i<=n;i++)
		{
			if(dye[i])
			continue;
			for(int j=1;j<=6;j++)
			{
				dye[i]=j;
				dfs(cur+1);
				dye[i]=0;
			}
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	while(m--)
	{
		scanf("%d%d",&x,&y);
		mp[x][y]=1;
		mp[y][x]=1;
	}
	dfs(1);
	printf("%d",ans);
}
就算是一分钱，也是对作者极大的支持
------ 本文结束 ------

版权声明

Baccano by baccano is licensed under a Creative Commons BY-NC-ND 4.0 International License.
由baccano创作并维护的Baccano博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证。
本文首发于baccano 博客（ http://baccano.fun ），版权所有，侵权必究。

小游戏

---小游戏:要不要来选择一下自己可能的老婆？---

简易发声器

---简易的七键钢琴插件---

可以使用鼠标点击琴键也可以使用主键盘1-7或者小键盘的1-7来操作

那么现在开始吧

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
0%