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 
*/

相关内容

热门资讯

oppo安卓11.1系统新功能... 你知道吗?最近OPPO手机又来了一次大升级,安卓11.1系统的新功能简直让人眼前一亮!今天,就让我带...
win10系统和安卓系统的,全... 你有没有发现,现在手机和电脑的操作系统真是五花八门,让人挑花了眼?今天,咱们就来聊聊两个超级热门的系...
安卓怎么设置重力系统,安卓重力... 你有没有发现,有时候手机屏幕上的图标会自动旋转,就像有看不见的小手在帮你翻书一样?这就是安卓手机的重...
图片管家推荐安卓系统,图片管家... 手机里的图片是不是越来越多,乱糟糟的找不到?别急,今天就来给你安利一款超好用的安卓系统图片管家——它...
安卓2.3系统宣传片,无限可能 你有没有注意到,手机的世界里,有时候一个小小的系统更新就能掀起一阵热潮呢?今天,就让我带你穿越回那个...
有关安卓和苹果系统提问,全面对... 你有没有想过,为什么你的手机里装的是安卓系统,而你的朋友用的是苹果?是不是好奇这两个系统有什么不同?...
安卓系统清理排行榜,助你手机焕... 手机里的安卓系统是不是越来越慢了?别急,今天就来给你揭秘一下安卓系统清理排行榜,让你手机瞬间恢复活力...
安卓系统app自动启动不了,安... 手机里的安卓系统APP突然不自动启动了,这可真是让人头疼啊!你是不是也遇到了这种情况?别急,今天就来...
ios系统和安卓系统哪个才是未... 说到手机操作系统,你是不是也和我一样,对iOS系统和安卓系统哪个才是未来充满了好奇呢?毕竟,这两个系...
最丝滑的安卓系统,最丝滑安卓系... 你有没有想过,手机系统就像是我们生活中的调味品,有时候平淡无奇,有时候却让人回味无穷。今天,就让我带...
笔记本安卓系统下载,下载与使用... 你有没有想过,你的安卓笔记本也能拥有一个全新的操作系统呢?没错,就是那种可以让你在笔记本上畅游安卓世...
老年人安卓手机系统,畅享智能生... 你有没有发现,身边越来越多的老年人开始玩起了智能手机呢?这不,最近我注意到,他们中很多人选择了安卓手...
安卓手机系统大改造,重塑未来 你有没有发现,最近你的安卓手机好像变得不一样了?没错,安卓手机系统正在经历一场大改造,就像换上了新装...
能安装安卓应用的系统,探索无限... 你有没有想过,为什么你的手机可以安装那么多好玩的应用,而电脑就只能用那些固定的软件呢?其实,现在有一...
安卓系统备份备忘录,轻松备份与... 你有没有想过,那些藏在安卓手机里的备忘录,它们就像是你生活中的小秘密,随时准备着为你提供帮助?今天,...
欧沃手机安卓系统,畅享智能生活... 你有没有发现,最近手机市场又掀起了一股热潮?没错,就是欧沃手机!这款手机凭借其出色的性能和亲民的价格...
安卓4.4系统tv软件,探索安... 亲爱的读者们,你是否曾为家里的电视屏幕增添一些智能的魔力而烦恼?别担心,今天我要给你带来一个超级实用...
安卓系统的研究人物,安卓系统发... 你知道吗?在科技飞速发展的今天,安卓系统可是占据了智能手机市场的大半壁江山。而在这片广阔的天地里,有...
山寨苹果刷会安卓系统,安卓系统... 你知道吗?在科技圈里,总有一些让人眼前一亮的小秘密。今天,我要给你揭秘一个关于山寨苹果刷安卓系统的神...
安卓系统新用户登录,畅享智能生... 你刚刚入手了一台全新的安卓手机,是不是有点小激动呢?别急,别急,让我来给你详细介绍一下安卓系统新用户...