cover1100:技巧，没有模拟20样例给我滚一边子去
4 A. Kalevitch and Chess
我做的话先遍历每一行，然后遍历每一列，如果全都是一样的字母，那就加一（这里应该会去写个函数，然后不行就直接return false）然后如果是行是八个了，那就列归为零 最后输出
但是这里不用分别更新列和行，也没有必要就是说去写个函数，如果是黑色，就加一，如果是八了，那就直接行的结果加1，列只在第一行更新，当然如果最后是八个，直接结果更新为八就行（这里千万不要再写函数了，用和来判断就行）
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
//模拟、递推（规律）、枚举、贪心、递归（搜索）
#define endl '\n'
#define hkn ios::sync_with_stdio(false),cin.tie(nullptr);
#define l scanf
#define z printf
char ch[10][10];
int main(){
int a = 0, b = 10;
for(int i = 0;i < 8;i ++){
cin >> ch[i];
int cnt = 0;
for(int j = 0;j < 8;j ++){
if(ch[i][j] == 'B'){
cnt ++;
}
}
if(cnt == 8)a ++;
b = min(b,cnt);
}
int ans = a + b;
if(a == 8){
ans = 8;
}
cout << ans << endl;
return 0;
}
5. Lucky String
我只能说如果你想自己去模拟，那我也没有办法，自己一个去模拟的过程很麻烦，但是你只要稍微足够细心，你就能够发现规律，这个如果按照上面的方法去模拟上20个数据（实际上十个左右就能有很明显的规律）
四个一组重复循环的
一下是憨蛋写的代码：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
//模拟、递推（规律）、枚举、贪心、递归（搜索）
#define endl '\n'
#define hkn ios::sync_with_stdio(false),cin.tie(nullptr);
#define l scanf
#define z printf
string ansch ;
string res;
char ch[10][10];
int kkk[200];
int main(){
int n;cin >> n;
string ans;
if(n == 1) ans = 'a';
else if(n == 2)ans = "ab",kkk['a'] = 1,kkk['b'] = 2;
else if(n == 3) ans = "abc",kkk['c'] = 3;
else if(n == 4) ans = "abcd",kkk['d'] = 4;
else if(n == 5) ans = "abcda",kkk['a'] = 5;
else if(n == 6) ans = "abcdab",kkk['b'] = 6;
else if(n == 7) ans = "abcdabc",kkk['c'] = 7;
else{
ans = "abcdabc";
int cnt = 8;
while(cnt <= n){
char ch1,ch2;
ch1 = ans[cnt - 7 - 1];
ch2 = ans[cnt - 4 - 1];
if(ch1 < ch2 &&(cnt - kkk[ch1] == 4 || cnt - kkk[ch1] == 7)) ansch = ch1,kkk[ch1] = cnt;
else ansch = ch2,kkk[ch2] = cnt;
ans += ansch;
cnt ++;
}
}
cout << ans << endl;
return 0;
}
1. Mountain Scenery
一个很有意思的现象是这个题目过的人数要比第二个题目少很多，我刚开始也不慎掉入题目的陷阱，题目的意思是说就算是捣蛋也必须符合山峰的性质，可能很多人直接操作了，另外这个题目数组的长度也要格外的注意
开的时候是2 * n + 1
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
//模拟、递推（规律）、枚举、贪心、递归（搜索）
#define endl '\n'
#define hkn ios::sync_with_stdio(false),cin.tie(nullptr);
#define l scanf
#define z printf
const int N = 220;
int a[N];
bool st[N];
int main(){
int n,k;cin >> n >> k;
for(int i = 1;i <=2 * n + 1;i ++) cin >> a[i];
while(k --){
for(int i = 2;i <=2 * n;i += 2){
if(a[i] - 1 > a[i - 1] && a[i] - 1> a[i + 1] && !st[i]){
a[i] --,st[i] = true;
break;
}
}
}
for(int i = 1;i <=2 * n + 1;i ++) cout << a[i] << " ";
return 0;
}
2A. Dice Tower
如果可能唯一地确定塔中所有骰子面上的数字，请输出"YES"（不带引号）。如果不可能，则输出"NO"（不带引号）。
是的，以上就是这个题目关键
We know that in this tower the adjacent dice contact with faces with distinct numbers.
这两句话加起来就能解决这个题目
这个题目的正确理解方式是，如果说上面的点数是1或者7，第二个骰子的上下点数也是1或者7，这样就是存在唯一的排序方式的，但是如果说上面是1或者7，第二个是3 或者 4，这样的排序方式根本就是杂乱无章的，不知道到底是什么样子的
如何更加方便地模拟呢，一个是分类地时候尽可能把同一类的放在一起
在一个看看是yes的情况少还是no的情况少，用少的来做：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
//模拟、递推（规律）、枚举、贪心、递归（搜索）
#define endl '\n'
#define hkn ios::sync_with_stdio(false),cin.tie(nullptr);
#define l scanf
#define z printf
using namespace std;int main(){
int n,a;cin>>n>> a;
bool flag = false;
while(n --){
int x,y;cin >> x >> y;
if(!flag && x == a || x == 7 - a || y == a || y == 7 - a){
flag = true;
}
}
if(flag) cout << "NO" << endl;
else cout << "YES" << endl;
return 0;
}
这个题目很容易，很简单，但是我还是直觉就是模拟了，没有想到其实这个排个序会更加容易的做出来：
#include<bits/stdc++.h>
using namespace std;
int a[105],b,c,i,n,p;
int main(){
cin>>n;
for(i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);
cout<<"1 "<<a[0]<<endl;
if(a[n-1]>0){
cout<<"1 "<<a[n-1]<<endl;
cout<<n-2;
for(i=1;i<n-1;i++)
cout<<" "<<a[i];}
else{
cout<<"2 "<<a[1]<<" "<<a[2]<<endl;
cout<<n-3;
for(i=3;i<n;i++)
cout<<" "<<a[i];}}
4 A. Vasya and Digital Root
这个做出来的人可能也是比较少的可能是因为被答案迷惑了，好不好理解不说，逗号表达式非常好用
#include <iostream>
#include <cmath>
using namespace std;
int main(){
int n,m;cin >> n >> m;
if(m == 0 && n == 1) return cout << "0",0;
if(m == 0 && n != 1) return cout << "No solution",0;
cout << m;
n --;
while(n --) cout << 0;
}
5B. Fedor and New Game
这个题目算是补充了一个新的知识点，两个数字不同二进制位的数量就是两个数字异或得到的数字里面1的个数
#include <iostream>
using namespace std;
const int N = 110;int a[N];
int ans;
int res;
int main(){
int n,m,k;cin >> n >> m >> k;
for(int i = 1;i <= m + 1;i ++){
cin >> a[i];
}
int x = a[m + 1];
for(int i = 1;i <= m;i++){
int y = x ^ a[i];
res = 0;
while(y){
if(y & 1) res ++;
y >>= 1;
}
if(res <= k) ans ++;
}
printf("%d",ans);return 0;
}
1
534A
这个是答案代码：
#include<cstdio>
int n,i;main()
{scanf("%d",&n);
if(n<5)printf(n<3?"1\n1":n==3?"2\n1 3":"4\n2 4 1 3");
else {printf("%d\n",n);for(i=1;i<=n;i+=2)printf("%d ",i);for(i=2;i<=n;i+=2)printf("%d ",i);}}
这个是我的代码，看的出来，我的代码是比较麻烦的，增加了没有必要的分类，直接按顺序一步步输出就行了，没有必要分类
2
667B
这个题目就是纯感谢答案提示了：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int main(){
int n;cin >> n;
for(int i = 0;i < n;i ++) cin >> a[i];
sort(a,a + n);
int sum = 0;
for(int i = 0;i < n - 1;i ++){
sum += a[i];
}
if(a[n - 1] == sum) return cout << 1,0;
cout << a[n - 1] - sum + 1;
}
考虑最少的话，是去构建一个以给定最大边为最长边，1为最短边的等腰三角形，这个题目说到了多边形，那就先考虑三角形，说到了最短，那就考虑1行不行
3
638A
虽然这个题目上来一下子就做出来了，但是自己还是用的模拟，事实证明这个还是可以不用模拟：
#include<iostream>
main(){int n,a;std::cin>>n>>a;std::cout<<((a%2)?a/2+1:(n-a)/2+1);return 0;}
这个是存在朴素规律的，如果是奇数，就是除以2 加上1 这个很容易理解，毕竟是没有偶数了
如果是偶数，如果题目不让反过来的话，那就是(a - 1) / 2 + 1,但是这里反过来了，那就是用最大的减去一下就成立了
4
B. Guess the Permutation
这个没有想法是非常不应该的，观察样例不够仔细，如果说某一行里面全都是1和0，说明这一行所代表的数字是1，其他数字和我一相比，都比我小，所以说都是1，如果一行里最大就是2，说明这一行代表的数字是2，遇见3 4 5都是2，当然了遇见1可能是1，同样的道理，如果一行当中最大的是谁，这一行代表的就是谁，n - 1会出现两次，4遇见了5是4，5遇见其他的都是4
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 510;
int a[N][N];
int main(){
int n;cin >> n;
for(int i = 0;i < n;i ++){
for(int j = 0;j < n;j ++){
cin >> a[i][j];
}
}
int flag = 1;
for(int i = 0;i < n;i ++){
int ans = 0;
for(int j = 0;j < n;j ++){
ans = max(ans,a[i][j]);
}
if(ans == n - 1 && flag == 1){
cout << n << ' ';
flag ++;
}
else cout << ans << " ";
}
return 0;
}
5
609B
先枚举是哪两种，然后相乘就是方式
这个比较简单
1
1099B
这个题目首先我得夸夸我自己，发现了规律，其实规律就那点事，写写画画就没了，
其次我得夸夸这个题目，就是发现了规律还真的不一定能够写出代码
一般数组需要开很大很大是没有必要的 我发现了规律，但是不是很会模拟这个过程：
真的太美妙了
#include<iostream>
using namespace std;
typedef long long ll;
int main(){
ll n;cin >> n;
ll a = 1,b = 1;
ll ans = 0;
for(int i = 1;i <= n;i ++){
if(a * b >= n){
ans = a + b;
break;
}
if(a < b) a ++;
else b ++;
}
cout << ans << endl;
}
2
看似很吓人，实则很简单
3
这个题目收获巨大：和斐波那契那个题目一样，正着方向来我们行不通，我们就看后面的方向，从后向前推，然后看看第一天行不行
其实要是单独看某一天的化这个是没有问题的，可以是奇数也可以是偶数，但是要是看全局，就要照顾着点了，我们想最后一天，实际都是可以的，如果是一个奇数，让前面一个减去1，然后往前捋着看，假设每天一天都是合理的（能这样做的原因是每一天都可以是奇数也可以是偶数），一直到第二个，如果第二个是奇数，那还是需要减去1，如果是偶数那就不用减去1，我们按理说已经减去了第一天上的那个奇数带来的1，此时1应该是个偶数，正好符合和第二个减去的那个，这样的结果就是正确的，但是如果说第一个数字要是一个奇数，那就是错误的
#include<bits/stdc++.h>
using namespace std;
int n,a[202000];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=n;i>=2;i--)
{
if(a[i]<0)
{
cout<<"NO";
return 0;
}
if(a[i]%2)
{
a[i-1]--;//前一项
}
}
if(a[1]%2)cout<<"NO";
else cout<<"YES";
return 0;
}
4
这个是冒泡排序哥哥
1A. Alyona and Numbers
量变引起质变的第一个特征，遇见重复的题目 这个和acwing上的题目是一样是，如果我们直接枚举两个变量是不行的，这时候我们就要想能不能减少枚举元素 答案是可以的
这个不是转化枚举对象，之前的认识是不对的，这个不是转换枚举对象
#include<iostream>
using namespace std;
const int N = 1000000+ 10;
long long sn[5],sm[5];
int main(){
int n,m;cin >> n >> m;
for(int i = 1;i <= n;i ++){
sn[i % 5] ++;
}
for(int i = 1;i <= m;i ++) sm[i % 5] ++;
long long ans = sn[0] * sm[0];
for(int i = 1;i <= 5;i ++){
ans += sn[i] * sm[5 - i];
}
cout << ans << endl;
return 0;
}
2B 1166B - All the Vowels Please
如果说这个东西本身是小于5行5列的正方形肯定是不行的，所以首先要保证这个东西应该是大于5 * 5的，其次，如果是一个素数，根本就分割不成n * m的正方形，所以先保证大于5行5列，然后分割成边分别是大于n或者大于m的正方形，但是这里有意非常好的做法，n的基础是5，我们慢慢的增加，当超过了k或者说遇见了能够整除的我们就停止加，最后判断:
#include<iostream>
using namespace std;
int main(){
int k,n=5;
//就拿42和41来说
//如果上来输入41的化
for(scanf("%d",&k); n*n<k&&k%n; n ++);
//cout << n << endl;
if(n*n > k) puts("-1");
else
while(k--)
putchar("aeiou"[(k/n+k%n)%5]);
return 0;
}
3C
对于任意的实数 a、b、c、d 都满足不等式 |a - b| + |c - d| >= |a + c - b - d|。
1
B. Knights
求最大最多，一个是可以无赖看样例猜一下最大值，一个是我们贪心的想，怎么样怎么样是最大值，我们发现每个点实际上只有两个或者四个点可以是相互攻击到的，所以说我们想办法就是说让每个点都能满足要求，通过观察，如果坐标之和是奇数的放在一起，偶数的放在一起，这样就是可以进行的，所以这种方格以后一点和坐标i,j联系起来
#include <iostream>
using namespace std;
int main(){
int n;cin >> n;
for(int i = 1;i <= n;i ++){
for(int j = 1;j <= n;j ++){
if((i + j) % 2){
cout << "B";
}
else{
cout << "W";
}
}
cout << '\n';
}
return 0;
}
2
这个题目考察的是stl的set，该说不说，这个做法非常简洁，所以以后也要好好掌握着个set
1B. AND Sorting
有的时候题目说是求最大的，但是我们并不要被最大而迷惑了，不一定就是说都是最大的，有可能就是满足所有条件的一个值
只有pi & pj == x才能就是说两者交换，但是所有不在自己对应位置上的数字至少是移动一次，所以说所有的数字相与，然后这个值就是x，所有的数字对应位置上都是1，这样的x才能符合所有数字的要求
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,a[N],p;
int main(){
int T;scanf("%d",&T);
while(T--){
int ans = -1;
scanf("%d",&n);
int x;
for(int i = 0;i < n;i ++){
cin >> x;
if(x != i && ans >= 0){
ans &= x;
}
if(x != i && ans < 0){
ans = x;
}
}
cout << ans << endl;
}
return 0;
}
这个题目的重点从来就不是最大值
2B. Binary Period
这里讨论一下B题目的做法，昨天晚上打比赛的这个题目能做出来的原因是
https://codeforces.com/contest/1855/problem/B昨天晚上的题目
虽然样例没有看明白但是自己去尽可能考虑除了样例之外从1开始越来越大的情况 于是发现了规律，做出来了
也就是说题目本身会迷惑我们，所以我们应该抛开题目来尽可能的发现一般朴素性质的规律
这个题目我们枚举周期，我们发现周期最小就是1，然后就是2
#include <iostream>
using namespace std;
bool check(string s){
for(int i = 0;i < s.size() - 1;i ++){
if(s[i] != s[i + 1]) return false;
}
return true;
}
int main(){
int n;cin >> n;
while(n -- ){
string s;cin >> s;
if(check(s)){
cout << s << endl;
continue;
}
cout << s[0];
for(int i = 1;i < s.size();i ++){
if(s[i] == s[i - 1]){
if(s[i] == '0') cout << 1;
else cout << 0;
cout << s[i];
}
else{
cout << s[i];
}
}
cout << endl;
}
return 0;
}
3
1360C - Similar Pairs
关键点在于：
要么奇数个，要么偶数个，奇数个减去一个就变成了偶数个，只要是存在一对相差为1的就符合要求
4
因为奇数加奇数时偶数 偶数加偶数也是偶数，所有偶数的最大公约数应该是2 ,所以我们就按照这个奇数偶数相同的原则来进行选择
#include <bits/stdc++.h>
using namespace std;
const int maxn=2009;
int t,n;
int a[maxn],ji[maxn],ou[maxn],top1,top2;
int main()
{
int t;
cin>>t;
while(t--)
{
top1=top2=0;
cin >> n;
for(int i=1;i<=n*2;i++)
{
cin >> a[i];
if(a[i]%2==0) ou[++top2]=i;
else ji[++top1]=i;
}
if(top1%2==0)
{
if(top2>=2)//偶数多于2,舍弃2个偶数
{
for(int i=4;i<=top2;i+=2) cout<<ou[i-1]<<" "<<ou[i]<<endl;
for(int i=2;i<=top1;i+=2) cout<<ji[i-1]<<" "<<ji[i]<<endl;
}
else//奇数多于2,舍弃2个奇数
{
for(int i=4;i<=top1;i+=2) cout<<ji[i-1]<<" "<<ji[i]<<endl;
for(int i=2;i<=top2;i+=2) cout<<ou[i-1]<<" "<<ou[i]<<endl;
}
}
else//舍弃一奇一偶
{
for(int i=3;i<=top1;i+=2) cout<<ji[i-1]<<" "<<ji[i]<<endl;
for(int i=3;i<=top2;i+=2) cout<<ou[i-1]<<" "<<ou[i]<<endl;
}
}
}
5
读题的时候要是目标还是条件
这里是目标，不是满足这个条件才能进行移动，是移动后满足这个条件
#include <iostream>
using namespace std;
const int N = 110;
int a[N];
int main(){
int t;cin >> t;
while(t --){
int n;cin >> n;
for(int i = 0;i < n;i ++) cin >> a[i];
for(int i = 0;i < n;i ++){
if(a[i] == 0) {
cout << 0 << " ";
continue;
}
if((i & 1) == 0){
cout << abs(a[i]) << " ";
}
else{
cout << "-" << abs(a[i]) << " ";
}
}
cout << endl;
}
return 0;
}
1407A - Ahahahahahahahaha
这个题目有n / 2的限制，还要注意到除了2就是1，所以我们尽可能把眼光放得长远一些，不要看具体怎么操作，这也是关键，总想着具体怎么模拟，每一步应该怎么做就容易做不出来，b题不是模拟题
这里很容易，因为n / 2,而且除了1就是0，所以谁少删除谁不就完了
1421B - Putting Bricks in the Wall
锻炼构造题目的好处就是这玩意帮你找到题目的眼，那个地方是解决问题的关键所在，一眼看到
C. Ping-pong
这个题目的题眼是这个，我们只需要最大化每个人胜利的次数，不需要就是说管输的次数
Alice和Bob都会以最佳方式进行比赛，并希望首先最大化他们的获胜次数，其次最小化对手的获胜次数。
B. GCD Length
永远不要忘记去暴力枚举所有的答案，这个永远是最优答案
#include <iostream>
#include <cmath>
#include <bits/stdc++.h>
using namespace std;
int a[] = {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
int judge(int x){
int cnt = 0;
while(x){
cnt ++;
x /= 10;
}
return cnt;
}
int main(){
int t;cin >> t;
while(t --){
int x,y,z;cin >> x >> y >> z;
for(int i = a[x - 1];i <= a[x] - 1;i ++){
for(int j = a[y - 1];j <= a[y] - 1;j ++){
if(judge(__gcd(i,j)) == z){
cout << i << " " << j << endl;
goto lz;
}
}
}
lz:;
}
return 0;
}
这里上次学会的去优化的方式 我们不用pow这个函数由精度损失的可能性
扫一扫
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
