Codeforces Round #740 (Div. 2)
admin
|
|
229
|
Codeforces

1935 字
|
22 分钟

Codeforces Round #740 (Div. 2, based on VK Cup 2021 – Final (Engine))

Simply Strange Sort

题目描述：

定义f(i)为如果a[i] > a[i + 1]则交换a[i]与 a[i + 1]

你从num = 1开始执行以下操作，直到所有数已经按升序排好了

  • 如果num是奇数，就进行f(1),f(3),…,f(n−2)的操作;
  • 如果num是偶数，就进行f(2),f(4),…,f(n−1)的操作

思路：

直接模拟即可，有个好用的函数叫is_sorted(),可以按照你想的方式判断是否排好序

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define eps 1.0E-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX  1000 + 50
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define max(a,b) (((a)>(b)) ? (a):(b))
//#define min(a,b) (((a)>(b)) ? (b):(a))
typedef  long long ll ;
typedef unsigned long long ull;
//不开longlong见祖宗!不看范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int t;
int n, m;
int tr[1005];

void work(){
    sd(n);
    for(int i = 1; i <= n; ++i)sd(tr[i]);
    int ans = 0;
    int num = 0;
    while (!is_sorted(tr + 1, tr + 1 + n)) {
        ++ans;
        ++num;
        if(num & 1){
            for(int i = 1; i <= n - 2; i += 2){
                if(tr[i] > tr[i + 1])swap(tr[i], tr[i + 1]);
            }
        }
        else{
            for(int i = 2; i <= n - 1; i += 2){
                if(tr[i] > tr[i + 1])swap(tr[i], tr[i + 1]);
            }
        }
    }
    cout<<ans<<endl;
}

int main(){
    sd(t);
    while (t--) {
        work();
    }
    return 0;
}

B. Charmed by the Game

题目描述：

A和B打棒球比赛，A发球，如果A赢了，就叫“hold”，如果B赢了，就叫“break”；同样的，B发球，如果B赢了，就叫“hold”，如果A赢了，就叫“break”

轮流发球，但谁先手不知道，现在知道A赢了a局，B赢了b局，你想知道所有的break的不同次数分别是多少，从小到大输出

思路：

这个题是个思维题，有点绕

这里先讲一下t神的思路：

这里假设A先手，总比赛数量是a+b局，如果a+b是偶数，那A和B都是进行局，如果是奇数，此时因为是A先手，则A进行局，B进行局，设x为A发球时B赢(即break)的次数(0<=x<=p)，y为B发球时A赢(即break)的次数(0<=y<=q)，A赢的游戏数为a = (p – x) + y，我们既不知道x，也不知道y，但是我们可以枚举x的值，得出y的值，判断y的值合法不，然后x+y就是当前的brear数量，搞个set塞进去就行

B先手也是一样

不过t神直接给了个最终的式子，（但是我不知道怎么用上面的思路推出来的，公式如下：

  • Let d=⌊|a−b|2⌋.
  • If a+b is even, all possible values of k are d,d+2,d+4,…,a+b−d.
  • If a+b is odd, all possible values of 𝑘k are d,d+1,d+2,…,a+b−d.

再讲讲我的思路：

我是这样想的，最小值和最大值我可以算出来，然后交换任意一个没有交换过的A和B的位置，就能使得break的数量+2或者-2，最小值就往上+2，最大值就往下-2，加减的个数就是能交换的次数，就是min(a,b)，然后就扔进set里面，按要求输出即可

那现在的问题就是算出最小值和最大值

设maxn=max(a, b), minx = min(a, b)

  • 最小值：

    怎么想呢？最小值就是让break尽可能少，就让谁发球谁就尽可能赢，这样使得hold的数量最大，则break的数量就是最小，所以minx*2的部分都是hold，剩下的maxn-minx的部分，只有一半是能成的，因为发球是轮流来的，再加上你可以调节先手是谁，且是找最小值，所以是向下取整数

  • 最大值：

    最大值好解释，前2 * minx个都对着干，A发球就让B赢，B发球就让A赢，剩下的maxn-minx个和上面的一样，不过这次是求最大值，所以可以调整先手位置获得更大的那个，也就是向上取整

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define eps 1.0E-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX  1000 + 50
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define max(a,b) (((a)>(b)) ? (a):(b))
//#define min(a,b) (((a)>(b)) ? (b):(a))
typedef  long long ll ;
typedef unsigned long long ull;
//不开longlong见祖宗!不看范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int t;
int n, m;
int minx, maxn;

void work(){
    set<int>se;
    cin>>n>>m;
    minx = min(n, m);
    maxn = max(n, m);
    int num = 2 * minx + (maxn - minx + 1) / 2;
    se.insert(num);
    int a = minx;
    while (a--) {
        num -= 2;
        se.insert(num);
        if(num < 0)break;
    }
    num = (maxn - minx) / 2;
    se.insert(num);
    a = minx;
    while (a--) {
        num += 2;
        se.insert(num);
        if(num < 0)break;
    }
    set<int>::iterator it;
    cout<<se.size()<<endl;
    for(it = se.begin(); it != se.end(); ++it)cout<<*it<<' ';
    cout<<endl;
}

int main(){
    io;
    cin>>t;
    while (t--) {
        work();
    }
    return 0;
}

C. Deep Down Below

题目描述：

给出n个关卡，再给出每个关卡的怪物数量、及其护盾值，你可以从任意关卡出发，去打任意关卡，每关只能打一次，打关卡的时候，只有你当前的攻击力大于目前的怪物才能打死他，每打死一个怪会获得永久的1点攻击力加成，问你最开始需要多少攻击力才能通过所有关卡

思路：

每个关卡都有不定的怪物，我们可以确定出打当前关卡所需的最小攻击力，也就是max{ai + 1 + (i – 1)}即max{ai – i + 2},记做maxn然后对其从小到大排个序，在从小开始贪心即可，贪心的时候就判断当前的攻击力是否大于克服maxn，如果大于，那就直接给攻击力加上关卡的怪物数量num，如果不大于，就给攻击力赋值为maxn，在给ans + maxn – num，最后输出ans即可

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define eps 1.0E-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX  200000 + 50
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define max(a,b) (((a)>(b)) ? (a):(b))
//#define min(a,b) (((a)>(b)) ? (b):(a))
typedef  long long ll ;
typedef unsigned long long ull;
//不开longlong见祖宗!不看范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int t;
int n, m, x, sum;
struct ran{
    int d, maxn, end;
}tr[MAX];

bool cmp(ran a, ran b){
    if(a.maxn != b.maxn)return a.maxn < b.maxn;
    else return a.end > b.end;
}

void work(){
    sum = 0;
    sd(n);
    for(int i = 1; i <= n; ++i){
        sd(tr[i].d);
        sum += tr[i].d;
        tr[i].maxn = 0;
        for(int j = 1; j <= tr[i].d; ++j){
            sd(x);
            tr[i].maxn = max(tr[i].maxn, x + 2 - j);
        }
        tr[i].end = tr[i].maxn + tr[i].d;
    }
    sort(tr + 1, tr + 1 + n, cmp);
    int ans = tr[1].maxn;
    int num = tr[1].end;
    for(int i = 2; i <= n; ++i){
        if(num < tr[i].maxn){
            ans += tr[i].maxn - num;
            num = tr[i].end;
        }
        else{
            num += tr[i].d;
        }
    }
    cout<<ans<<endl;
}

int main(){
    sd(t);
    while (t--) {
        work();
    }
    return 0;
}

D1. Up the Strip (simplified version)

题目描述：

对数字x有两种操作：

  • 取[1, x-1]内任意一个数y，让x = x – y;
  • 取[2，x]内任意一个数y ，让x = x / y

现在问将n变成1的操作方案有多少种

思路：

两种操作方法，还是求方案数，显然是dp了

状态转移方程显然是：

第一个求和的很简单，用前缀和即可，后面那个乍一看没有思路

但想一想可以发现，涉及向下取整，又有区间，是数论分块

根据数论分块：，i是从2开始，那l也是从2开始， ,然后对于区间[l, r]，他们的相同，所以这一整段区间的值都可以由dp[n/i]转移而来，所以我们可以写出状态转移方程：

//顺序遍历

//逆序遍历

记得要加上那个前缀和或者是后缀和

分这两种遍历思路，其实都是可以，顺序遍历的思路是dp中：我是由谁推来的，即我是受谁影响的；逆序遍历的思路是dp中：我可以推向谁，即我可以影响谁。这都是一样的，只不过逆序是和题意一样的，比较好理解

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;

#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX  200000 + 50
//#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define loop(i, a, b) for (int i = (a); i < (b); i++)
#define dwn(i, a, b) for (int i = (a); i >= (b); i--)
#define mem(a,b) memset((a),(b),sizeof(a))
#define max(a,b) (((a)>(b)) ? (a):(b))
#define min(a,b) (((a)>(b)) ? (b):(a))

typedef  long long ll ;
typedef unsigned long long ull;
//不开longlong见祖宗!不看范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int n, mod;
ll dp[MAX];
ll sum[MAX];

void work(){
    sdd(n, mod);
  //逆序
    dp[n] = 1;
    for(int i = n; i >= 1; --i){
        dp[i] =  (dp[i] + sum[i + 1]) % mod;
        sum[i] = (sum[i + 1] + dp[i]) % mod;
        for(int l = 2, r; l <= i; l = r + 1){
            r = i / (i / l);
            dp[i / l] = (dp[i / l] + dp[i] * (r - l + 1) % mod) % mod;
        }
    }
    cout<<dp[1]<<endl;
  //顺序
//    dp[1] = sum[1] = 1;
//    for(int i = 2; i <= n; ++i){
//        dp[i] = sum[i - 1];
//        int num = i / 2;
//        int l = 2, r = i / num;
//        while (1) {
//            dp[i] = (dp[i] +  dp[num] * (r - l + 1) % mod) % mod;
//            if(num == 1)break;
//            l = r + 1;
//            num = i / l;
//            r = i / num;
//        }
//        sum[i] = (dp[i] + sum[i - 1]) % mod;
//    }
//    cout<<dp[n]<<endl;
}

int main(){
    work();
    return 0;
}

 

博客内容均系原创，未经允许严禁转载！
cf
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																					

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
Codeforces Round 770 (Div. 2) B – Fortune Telling 「奇偶性」「思维」

							
							

							
Codeforces Round 760 (Div. 3) E. Singers‘ Tour「思维」「线性代数」「构造」

							
							

							
CodeForces – 437

							
							

							
Codeforces Round #739 (Div. 3)

							
							

							
Codeforces Round #719 (Div. 3)