Codeforces Round 857 (Div. 2)【A-C】
创始人
2024-06-01 05:39:38
0

文章目录

  • A. Likes【贪心、模拟】
  • B. Settlement of Guinea Pigs【贪心】
  • C. The Very Beautiful Blanket【构造、观察】

链接
传送门

A. Likes【贪心、模拟】

分析
为了使得当前时间点赞的尽可能大,那么前面的赞的数目也要尽可能大,所以前面把能赞的都要先赞上,尽管后面撤赞了也使得其相对更大。为了使得每个点的赞仅可能小,前面留下的赞也要仅可能小,所以前面赞完之后马上要撤赞,即使后面不得不要点赞也可以保证此时最小。只需要模拟一下即可,统计一下,只赞不撤和又赞又撤的情况数目,模拟一下即可。
实现

#include 
#define ll long long
#define ls (u << 1)
#define rs (u << 1 | 1) 
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef pair PII;
const int N = 1005, M = 1e6 + 5;
int a[N], b[N];
void solve() {int n;cin >> n;for (int i = 1; i <= n; i++) a[i] = b[i] = 0;for (int i = 1; i <= n; i++) {int c;cin >> c;if (c > 0) a[c] = 1;else b[-c] = 1;}int cnt1 = 0, cnt2 = 0;for (int i = 1; i <= n; i++) {if (a[i] && !b[i]) cnt1++;//只赞if (a[i] && b[i]) cnt2++; //又赞又撤}int p = 0, t1 = cnt1 + cnt2, t2 = cnt2;//t1表示前面递增的长度for (int i = 1; i <= n; i++) {if (i != 1) cout << ' ';if (t1) cout << ++p, t1--;else if (t2) cout <<  --p, t2--;}cout << '\n';int m1 = 2 * cnt2, m2 = cnt1, q = 0;//m1表示前面又赞又撤的长度for (int i = 1; i <= n; i++) {if (i != 1) cout << ' ';if (i <= m1) {cout << (i & 1 ? 1 : 0);} else {cout << ++q;}}cout << '\n';
}
int main() {ios::sync_with_stdio(false);cin.tie(0);int T = 1;cin >> T;while (T--) {solve();}
}

B. Settlement of Guinea Pigs【贪心】

分析
这题本身不难。创建两个变量,cnt表示当前的豚鼠的数目,tmp表示最坏的情况(至少需要多少个笼子),如果说医生还没有来的话,多一个豚鼠,就需要多一个笼子,如果医生来的话就可以鉴定了,例如我们有100只豚鼠,性别已知,数目情况下数目最多,答案是一只异性,其余同性,1 + (99 + 1) / 2,共需要51个笼子,为什么呢?可以这样想,对于装满两只的笼子,这个笼子里是什么性别并不重要,反正是装满了,所以多余所有的情况都可以转化位,要么全部同性,要么有一只异性,全部同性,可能是有一个是一只笼子的,这样把他转话为异性,也不会增加笼子数,刚好整装,那么有一个异性则是可以增加一个笼子,为了确保这样的情况,所以我们就单取出一只异性即可。
实现

#include 
#define ll long long
#define ls (u << 1)
#define rs (u << 1 | 1) 
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef pair PII;
const int N = 1005, M = 1e6 + 5;
void solve() {int n;cin >> n;int ans = 0, cnt = 0, tmp = 0;for (int i = 1; i <= n; i++) {int c;cin >> c;if (c == 1) cnt++, tmp++;else {if (cnt) {tmp = 1 + cnt / 2;}}ans = max(tmp, ans);}cout << ans << '\n';
}
int main() {ios::sync_with_stdio(false);cin.tie(0);int T = 1;cin >> T;while (T--) {solve();}
}

C. The Very Beautiful Blanket【构造、观察】

分析
乍一看,你可能觉得这是什么用脚造的数据,太毒瘤了,但是实际上不是的。
在这里插入图片描述
观察一下我们就可以发现,每个数都是由一个子矩阵
0 1
2 3
加上一个数得到的,我们还可以发现所有的2*2的矩阵异或和都为零。那么加多少呢
如果说,我们不考虑数不能重复,那么我们可以这样构造。
0 1 0 1 0 1
2 3 2 3 2 3
0 1 0 1 0 1
2 3 2 3 2 3
对于相邻两个我们加多少合适,写成二进制。
000 001 100 101
010 011 110 111
可以发现,加4是合理的,对于中间四个而言,4的那一位是独立的,
0 4
0 4 这样对应位的异或和也是0,一位4的位数比较高,而且不影响末尾的0 1 2 3,那么下一行加多少呢,由于有200列,我们选择加一个大的2的幂,不影响最低位。
对于加粗部分的矩阵,虽然每两行之间是有差值的,但是两列(奇数列(1,3,5列)在前)之间必然是1,一个是偶数,一个是对应偶数加1,异或之后就是1。两个1异或就是0。另外的奇数列在前就是上面加4的情况,即使这两行不是奇数行在前,由于同行加的高位的2的幂是相同的异或会抵消,就相当于
0 4
0 4
完毕。
实现

#include 
#define ll long long
#define ls (u << 1)
#define rs (u << 1 | 1) 
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef pair PII;
const int N = 205, M = 1e6 + 5;
ll a[N][N];
void solve() {int n, m;cin >> n >> m;a[1][1] = 0, a[1][2] = 1;a[2][1] = 2, a[2][2] = 3;for (int j = 3; j <= m; j++) {a[1][j] = a[1][j - 1] + 4;a[2][j] = a[2][j - 1] + 4; }for (int i = 3; i <= n; i++) {for (int j = 1; j <= m; j++) {a[i][j] = a[i - 2][j] + 4096;}}cout << n * m << '\n';for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cout << a[i][j] << " \n"[j == m];}}
}
int main() {ios::sync_with_stdio(false);cin.tie(0);int T = 1;cin >> T;while (T--) {solve();}
}
/*
1
4 4
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15 
*/

相关内容

热门资讯

安卓系统对比骁龙,性能与生态的... 你有没有想过,为什么你的手机里装的是安卓系统,而不是苹果的iOS呢?又或者,为什么你的安卓手机里搭载...
qt程序安卓系统运行,基于Qt... 你有没有想过,为什么有些手机上的程序运行得那么顺畅,而有些却总是卡得让人抓狂?今天,就让我来给你揭秘...
安卓系统免费应用推荐,助你畅享... 手机里的应用是不是越来越多,有时候都挑花眼了呢?别急,今天我就来给你推荐一些安卓系统上的免费应用,让...
安卓系统视频通话app,打造无... 你有没有发现,现在手机上的视频通话功能越来越强大了?尤其是安卓系统上的那些视频通话app,简直让人爱...
安卓系统发现高危病毒,守护手机... 亲爱的手机用户们,最近可是有个大消息在安卓系统用户群里炸开了锅!没错,就是安卓系统发现了一款高危病毒...
安卓系统疯狂弹广告,揭秘广告软... 你有没有遇到过这种情况?手机里突然弹出一个广告,让你瞬间心情大崩溃?没错,说的就是安卓系统那让人头疼...
ebook 10进入安卓系统 你有没有发现,最近你的安卓手机里多了一个新伙伴——那就是电子书(ebook)10!没错,就是那个我们...
安卓系统如何调听筒,安卓系统调... 手机听筒声音突然变小了?别急,让我来教你如何轻松调教安卓系统的听筒,让它重新恢复活力!一、检查音量设...
安卓系统是怎么手机,解锁智能生... 你有没有想过,我们每天不离手的安卓手机,它背后的安卓系统究竟是怎么一回事呢?今天,就让我带你一探究竟...
安卓系统能代替windows系... 你有没有想过,我们日常使用的安卓系统和Windows系统,哪个才是真正的霸主呢?是不是有时候觉得安卓...
lp108安卓系统,功能特点与... 你有没有听说最近LP108安卓系统火得一塌糊涂?没错,就是那个让无数手机用户都为之疯狂的新系统!今天...
安卓系统挂载u盘,轻松实现数据... 你有没有想过,你的安卓手机或平板电脑突然变成了一个移动的U盘?没错,就是那种可以随意存取文件的神奇设...
i5 安卓系统,引领智能终端新... 你有没有想过,为什么你的手机总是卡得要命,而别人的手机却能流畅如丝?是不是因为你的手机搭载了那个传说...
安卓手机系统没有升级,揭秘潜在... 你有没有发现,你的安卓手机系统好像好久没升级了呢?是不是觉得有点out了?别急,今天就来给你详细聊聊...
安卓14系统定制v,创新功能与... 你知道吗?最近安卓系统又出新花样了!安卓14系统定制版V,这名字听起来就让人兴奋不已。今天,就让我带...
手机安卓系统越高越好,探索最新... 你有没有发现,每次手机更新系统,你的手机就像脱胎换骨了一样?没错,说的就是你,那个安卓手机!今天,咱...
鸿蒙系统怎么用回安卓,轻松实现... 你是不是也和我一样,对鸿蒙系统的新鲜感还没过,却又忍不住想回到熟悉的安卓世界?别急,今天就来手把手教...
苹果7跟安卓系统,性能对决与用... 你有没有想过,为什么苹果7那么受欢迎,而安卓系统却有着庞大的用户群体?今天,我们就来聊聊这个话题,看...
安卓手机刷简化系统,轻松实现流... 你有没有想过,你的安卓手机其实可以变得更加轻快、流畅呢?没错,就是通过刷简化系统!今天,就让我带你一...
社保掌上通安卓系统,轻松掌握在... 你有没有发现,现在的生活越来越离不开手机了?无论是购物、聊天还是办公,手机都能轻松搞定。这不,今天就...