首页 > 其他分享 >Educational Codeforces Round 158 (Rated for Div. 2)

Educational Codeforces Round 158 (Rated for Div. 2)

时间:2023-11-26 09:22:57浏览次数:39  
标签:Educational Rated int 158 chip cnt cell chips create

Educational Codeforces Round 158 (Rated for Div. 2)

基本情况

A题很水,几分钟秒了。

B题想到一个解,被自己 hack 掉之后没有重新想,一直想在自己一开始的基础上改好,结果最后B都没拿下。

B. Chip and Ribbon

我的思路

其实也是找规律,根本没严谨地证明正确性。不应该一条路走到黑的

找到第一个比上一个小的数,再找到最后一个这样的数,求两者差值。

毫无逻辑,就只是刚好通过样例了,我手造一堆数据 hack 了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2e5 + 10;

int t, n;
long long ans = 0, cnt;
int c[N];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> t;
	while (t--)
	{
		int l = 0;
		ans = 0;
		cin >> n;
		for (int i = 1; i <= n; i++)
		{
			cin >> c[i];
			if (c[i] && !l)
				l = i;
		}
		if (n == 1)
		{
			cout << c[1] - 1 << endl;
		}
		else
		{
			if (l != 1)
			{
				ans++;
			}
			bool is_end = true;
			bool is_cnt = false;
			for (int i = l + 1; i <= n; i++)
			{
				int temp = c[i - 1];
				if (i - 1 == l && c[i - 1] == 1)
				{
					if (c[i] < c[i  - 1])
						is_cnt = true;
					continue;
				}
				while (c[i] < c[i - 1])
				{
					is_cnt = true;
					i++;
					if (i == n + 1)
					{
						is_end = false;
						break;
					}
				}
				ans += temp - c[i - 1];
			}
			if (is_end)
			{
				if (!(ans == 1 && l != 1 && !is_cnt))
				{
					ans += c[n];
				}
			}
			cout << ans << endl;
		}

	}
	return 0;
}

正解思路

At first, let's change the statement a bit: instead of teleporting our chip into cell \(x\), we create a new chip in cell \(x\) (it means that the chip does not disappear from the cell where it was located). And when we want to move a chip, we move any chip to the next cell. Then, \(c_i\) will be the number of times a chip appeared in the cell \(i\), and the problem will be the same: ensure the condition on each \(c_i\) by "creating" the minimum number of chips.

Let's look at value of \(c_1\). If \(c_1>1\), we have to create at least \(c_1−1\) new chips in cell \(1\). Let's create that number of chips in that cell.

Then, let's see how we move chips from the cell \(i\) to the cell \((i+1)\). If \(c_i≥c_{i+1}\), then all chips that appeared in the cell \((i+1)\) could be moved from the \(i\)-th cell, so we don't need to create any additional chips in that cell.

But if \(c_i<c_{i+1}\), then at least \(c_{i+1}−c_i\) chips should be created in the cell \((i+1)\), since we can move at most \(c_i\) chips from the left.

So, for every \(i\) from \(2\) to \(n\), we have to create \(\max(0, c_i - c_{i-1})\) chips in the \(i\)-th cell; and the number of times we create a new chip in total is

\[c_1 - 1 + \sum\limits_{i=2}^{n} \max(0, c_i - c_{i-1}) \]

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 200'000;
 
int t;
 
int main() {
    cin >> t;
    for (int tc = 0; tc < t; ++tc) {
        int n;
        cin >> n;
        vector <int> cnt(n);
        long long res = 0;
        int cur = 0;
        for (int i = 0; i < n; ++i) {
            cin >> cnt[i];
            if (cnt[i] > cur) 
                res += cnt[i] - cur;
            cur = cnt[i];
        }
        
        cout << res - 1 << endl;
    }
    return 0;
}

标签:Educational,Rated,int,158,chip,cnt,cell,chips,create
From: https://www.cnblogs.com/kdlyh/p/17856539.html

相关文章

  • Educational Codeforces Round 158 补题(A~D)
    A.思路找出最大耗油的路程即可ac代码#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;consti64inf=8e18;typedefpair<int,int>pii;voidsolve(){intn,x;cin>>n>>x;std::vector<int>v(n);f......
  • Educational Codeforces Round 158 (Rated for Div. 2)
    A.LineTrip题意是:有n个加油点,人要来回两趟,问你最少要多少油?usingnamespacestd;inta[100];voidsolve(){ intn,m; cin>>n>>m; for(inti=1;i<=n;i++)cin>>a[i]; intans=a[1]; for(inti=2;i<=n;i++){ ans=max(ans,a[i]-a[i-1]); } ans=max(ans,2*(m-......
  • Educational Codeforces Round 146 补题(A~C)
    EducationalCodeforcesRound146(RatedforDiv.2)A.Coins题目大意给你两个整数n和k,问你是否存在两个非负整数x和y,使得2⋅x+k⋅y=n成立思路裴蜀定理秒了,记得开longlongac代码#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;consti64in......
  • Educational Codeforces Round 158 (Rated for Div. 2) A-C
    A大致题意:有一条长度为x的直线公路,最开始你位于0号点并且此时你的油箱装满了油,公路有n个加油站,当你经过加油站的时候你可以在加油站加满油,每走一个单位需要花费1升油量,起始位置和终点没有加油站,请问你的油箱容量至少为多少升才可以够你跑一个来回。解题思路:我们的路径大致是......
  • 「杂题乱刷」CF1585B
    原题链接CF1585BArrayEversion题目简述现在有一个长度为\(n\)的序列\(a\),每次操作将\(a\)中不大于序列\(a\)中最后一个数的元素按照在\(a\)序列中的顺序放入\(b\)序列中,大于序列\(a\)中最后一个数的元素同样按照在\(a\)中的顺序放入\(c\)序列中,然后再将\(c......
  • CSE 158/258 设计与实现
    任务定于11月20日星期一完成,但请确保将解决方案上传到排行榜有规律地您应该提交两个文件:writeup.txt对每个任务的解决方案进行简要的纯文本描述;请在提交截止日期提前;这只是为了帮助我们遵循您的代码,不需要待详细说明。assignment1.py包含解决方案的工作代码的python文件。自动标......
  • Educational Codeforces Round 99 (Rated for Div. 2)
    https://codeforces.com/contest/1455很久没有vp了,感觉思维又僵化了A题直接看样例,直接猜是长度。B题首先如果是\(x=\frac{n(n+1)}{2}\),那么就是n否则如果\(x=\frac{n(n+1)}{2}+y\),分成两类y=n,ans=n+2,y<n,我们总可以找到前面一个替换,然后恰好的到n,选取z=n-y即可C题感觉比B......
  • Educational Codeforces Round 156 (Rated for Div. 2) ABCD
    EducationalCodeforcesRound156(RatedforDiv.2)ABCDA.SumofThree题意:给定正整数\(n\),判断是否存在正整数\(a\),\(b\),\(c\)满足:\(a+b+c=n\)。\(a\),\(b\),\(c\)均不是\(3\)的倍数。如存在,输出YES并构造一组方案,否则输出NO。思路:法一:我们分类讨论。根据......
  • Educational Codeforces Round 13 E
    tilian最开始看错了以为是可以任意选择两人or选择一人胜出但题意是可以选择下一个擂主是谁考虑dp的话我们显然需要记录一个state以及当前擂主是谁转移就是dp[state][i]=max(dp[state][i],dp[state(1<<j)][j]*a[i][j]+dp[state(1<<i)]*a[j][i])意义是我们枚举他后一个交......
  • Educational Codeforces Round 157 D
    tilian不太会这种题发现找到一个数就能确定整个序列然后转而发现前缀异或和b1^b2=a1b1^b3=a2...我们发现要是n为偶数时能直接求出b1从而确定整个序列而为奇数时我们无法确定b1我们思考拆位之后如果b1该位为0算出真实的异或后的01个数b1该位为1算出真实的......