Codeforces Round #662 (Div. 2) / contest 1393

2024-02-29 12:50

本文主要是介绍Codeforces Round #662 (Div. 2) / contest 1393,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

        • A Rainbow Dash, Fluttershy and Chess Coloring
        • B Applejack and Storages
        • C Pinkie Pie Eats Patty-cakes
        • D Rarity and New Dress
        • E1
        • E2


ABCDE1E2

( √:做出; ●:尝试未做出; ○:已补题 )


题目地址:https://codeforces.com/contest/1393



A Rainbow Dash, Fluttershy and Chess Coloring

题意:签到题

思路

代码

#define DIN freopen("input.txt","r",stdin);
#define DOUT freopen("output.txt","w",stdout);
#include <bits/stdc++.h>
#include <cstdio>
#define mem(a,b) memset(a,b,sizeof(a))
#define REP(i,a,b) for(int i=(a);i<=(int)(b);i++)
#define REP_(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef pair<int,int> P;
int read()
{int x=0,flag=1; char c=getchar();while((c>'9' || c<'0') && c!='-') c=getchar();if(c=='-') flag=0,c=getchar();while(c<='9' && c>='0') {x=(x<<3)+(x<<1)+c-'0';c=getchar();}return flag?x:-x;
}int main()
{int t=read();while(t--){int n=read();cout<<n/2+1<<endl;}return 0;
}



B Applejack and Storages

题意:要求维护若干条边,每次可以增加一条某个长度的边,或者删除一条某个长度的边,你需要在每次操作结束后回答,这些边是否可以组成一个正方形加一个长方形。

思路:动态维护两个数 n2 和 n4(分别表示可以组成两条相同的边的对数,以及可以组成四条相同的边的对数),因为只需要一个正方形一个长方形,所以只需要在 8 以内更改这两个数就行了。最后存在的条件是 n4>=2 || (n4>0 && n2>=2)

代码

#define DIN freopen("input.txt","r",stdin);
#define DOUT freopen("output.txt","w",stdout);
#include <bits/stdc++.h>
#include <cstdio>
#define mem(a,b) memset(a,b,sizeof(a))
#define REP(i,a,b) for(int i=(a);i<=(int)(b);i++)
#define REP_(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef pair<int,int> P;
int read()
{int x=0,flag=1; char c=getchar();while((c>'9' || c<'0') && c!='-') c=getchar();if(c=='-') flag=0,c=getchar();while(c<='9' && c>='0') {x=(x<<3)+(x<<1)+c-'0';c=getchar();}return flag?x:-x;
}const int maxn=1e5+5;
int a[maxn],n2=0,n4=0;
char s[10];void add(int x)
{a[x]++;if(a[x]==2) n2++;else if(a[x]==4) n2--,n4++;else if(a[x]==6) n2++;else if(a[x]==8) n2--,n4++;
}void del(int x)
{a[x]--;if(a[x]==1) n2--;else if(a[x]==3) n2++,n4--;else if(a[x]==5) n2--;else if(a[x]==7) n2++,n4--;
}int main()
{int n=read();REP(i,1,n){int x=read();add(x);}int q=read();while(q--){scanf("%s",s);int x=read();if(s[0]=='+') add(x);else if(s[0]=='-') del(x);puts((n4>=2 || (n4==1 && n2>=2))?"YES":"NO");}return 0;
}



C Pinkie Pie Eats Patty-cakes

题意:有很多饼干,要把他们排成一排,把两两相同的饼干之间的间距拿出来,取这所有间距之间的最小值,目标是要使这个最小值最大,问这个最小值最大是多少。

思路:一开始一直在想二分,后来想着想着发现,我们只需要考虑最多的饼干就行了,因为少的那些完全可以在充分满足 最多的饼干之后,以同样的间距插进去,因为它们不需要最多的那么多位置,所以一定可行。还需要考虑最多的饼干有多少种,然后把它们平均分进去,算一下间距就行了。

算间距的方法大概就是,假设有 tot 种最多的饼干,最多的饼干每种有 m 个,那么其中的一个的第一个就放在第一个位置,最后一个应该放在第 n-tot+1 个位置,然后中间平均放,然后计算间距即可。

代码

#define DIN freopen("input.txt","r",stdin);
#define DOUT freopen("output.txt","w",stdout);
#include <bits/stdc++.h>
#include <cstdio>
#define mem(a,b) memset(a,b,sizeof(a))
#define REP(i,a,b) for(int i=(a);i<=(int)(b);i++)
#define REP_(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef pair<int,int> P;
int read()
{int x=0,flag=1; char c=getchar();while((c>'9' || c<'0') && c!='-') c=getchar();if(c=='-') flag=0,c=getchar();while(c<='9' && c>='0') {x=(x<<3)+(x<<1)+c-'0';c=getchar();}return flag?x:-x;
}const int maxn=1e5+5;
int num[maxn];int main()
{int T=read();while(T--){int n=read();REP(i,1,n) num[i]=0;REP(i,1,n){int x=read();num[x]++;}int m=0;REP(i,1,n) m=max(m,num[i]);int tot=0;REP(i,1,n) tot+=num[i]==m;printf("%d\n",(n-m-tot+1)/(m-1));}return 0;
}



D Rarity and New Dress

题意:给你一块布,布上面每个方块有一个颜色,你要从布上面剪下一个呈 45° 的正方形,并且要求这个正方形的颜色只有一种,问有多少种剪法。以下这三种都是合法的 45° 的正方形:

(图片截图于 https://codeforces.com/contest/1393/problem/D)

思路:设 f(i, j) 表示以 (i, j) 作为底端的点,往上能延伸的正方形的最大边长,那么对于每个 f(i, j) ,假设它和它 上面、左上、右上、上上 之间有不一样的颜色,那么 f(i, j)=1;如果全都一样,那么就取上面四个的 f 中的最小值 minx,那么 f(i, j)=minx+1 。最后计算 f 的和就是答案。

代码

#define DIN freopen("input.txt","r",stdin);
#define DOUT freopen("output.txt","w",stdout);
#include <bits/stdc++.h>
#include <cstdio>
#define mem(a,b) memset(a,b,sizeof(a))
#define REP(i,a,b) for(int i=(a);i<=(int)(b);i++)
#define REP_(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef pair<int,int> P;
int read()
{int x=0,flag=1; char c=getchar();while((c>'9' || c<'0') && c!='-') c=getchar();if(c=='-') flag=0,c=getchar();while(c<='9' && c>='0') {x=(x<<3)+(x<<1)+c-'0';c=getchar();}return flag?x:-x;
}const int maxn=2005;
int f[maxn][maxn];
char s[maxn][maxn];int main()
{int n=read(),m=read();REP(i,1,n) scanf("%s",s[i]+1);REP(i,1,2) REP(j,1,m) f[i][j]=1;REP(i,3,n) REP(j,1,m){if(j==1 || j==m) {f[i][j]=1; continue;}if(s[i][j]!=s[i-1][j-1] || s[i][j]!=s[i-1][j] ||s[i][j]!=s[i-1][j+1] || s[i][j]!=s[i-2][j]){f[i][j]=1;continue;}int x=100000;x=min(x,f[i-1][j-1]);x=min(x,f[i-1][j]);x=min(x,f[i-1][j+1]);x=min(x,f[i-2][j]);f[i][j]=x+1;}LL ans=0;REP(i,1,n) REP(j,1,m) ans+=f[i][j];cout<<ans;return 0;
}



E1

题意

思路

代码




E2

题意

思路

代码


这篇关于Codeforces Round #662 (Div. 2) / contest 1393的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:https://blog.csdn.net/dragonylee/article/details/107875906
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/758854

相关文章

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数,每次操作将其分成2^q份,对于每一份内部的数进行翻转(逆序),每次操作完后输出操作后新序列的逆序对数。 图一:  划分子问题。 图二: 分而治之,=>  合并 。 图三: 回溯:

Codeforces Round #261 (Div. 2)小记

A  XX注意最后输出满足条件,我也不知道为什么写的这么长。 #define X first#define Y secondvector<pair<int , int> > a ;int can(pair<int , int> c){return -1000 <= c.X && c.X <= 1000&& -1000 <= c.Y && c.Y <= 1000 ;}int m

Codeforces Beta Round #47 C凸包 (最终写法)

题意慢慢看。 typedef long long LL ;int cmp(double x){if(fabs(x) < 1e-8) return 0 ;return x > 0 ? 1 : -1 ;}struct point{double x , y ;point(){}point(double _x , double _y):x(_x) , y(_y){}point op

Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内

题目点击打开链接 凸多边形A, 多边形B, 判断B是否严格在A内。  注意AB有重点 。  将A,B上的点合在一起求凸包,如果凸包上的点是B的某个点,则B肯定不在A内。 或者说B上的某点在凸包的边上则也说明B不严格在A里面。 这个处理有个巧妙的方法,只需在求凸包的时候, <=  改成< 也就是说凸包一条边上的所有点都重复点都记录在凸包里面了。 另外不能去重点。 int

2014 Multi-University Training Contest 8小记

1002 计算几何 最大的速度才可能拥有无限的面积。 最大的速度的点 求凸包, 凸包上的点( 注意不是端点 ) 才拥有无限的面积 注意 :  凸包上如果有重点则不满足。 另外最大的速度为0也不行的。 int cmp(double x){if(fabs(x) < 1e-8) return 0 ;if(x > 0) return 1 ;return -1 ;}struct poin

2014 Multi-University Training Contest 7小记

1003   数学 , 先暴力再解方程。 在b进制下是个2 , 3 位数的 大概是10000进制以上 。这部分解方程 2-10000 直接暴力 typedef long long LL ;LL n ;int ok(int b){LL m = n ;int c ;while(m){c = m % b ;if(c == 3 || c == 4 || c == 5 ||

2014 Multi-University Training Contest 6小记

1003  贪心 对于111...10....000 这样的序列,  a 为1的个数,b为0的个数,易得当 x= a / (a + b) 时 f最小。 讲串分成若干段  1..10..0   ,  1..10..0 ,  要满足x非递减 。  对于 xi > xi+1  这样的合并 即可。 const int maxn = 100008 ;struct Node{int

Codeforces 482B 线段树

求是否存在这样的n个数; m次操作,每次操作就是三个数 l ,r,val          a[l] & a[l+1] &......&a[r] = val 就是区间l---r上的与的值为val 。 也就是意味着区间[L , R] 每个数要执行 | val 操作  最后判断  a[l] & a[l+1] &......&a[r] 是否= val import ja

CSS实现DIV三角形

本文内容收集来自网络 #triangle-up {width: 0;height: 0;border-left: 50px solid transparent;border-right: 50px solid transparent;border-bottom: 100px solid red;} #triangle-down {width: 0;height: 0;bor

AtCoder Beginner Contest 370 Solution

A void solve() {int a, b;qr(a, b);if(a + b != 1) cout << "Invalid\n";else Yes(a);} B 模拟 void solve() {qr(n);int x = 1;FOR(i, n) FOR(j, i) qr(a[i][j]);FOR(i, n) x = x >= i ? a[x][i]: a[i][x];pr2(