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

题目链接

A：

题意：
给定一列数，要求执行一个操作，若a[i]>a[i+1]就swap这两者
但是奇数次只能操纵奇数位上的比如i=1,i=3,i=5…偶数次只能操纵偶数位上的比如i=2;i=4。。。。
询问你想要将这一列数变为有序的需要变多少次
思路：
看了下数据：1e3就直接暴力了，但是要注意下面循环的时候不能开大了，一开始爆了TLE1就很离谱

//Author:Happy Dog
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        int a[1007];
        cin>>n;
        for(int i=1; i<=n; i++)
            cin>>a[i];
        int flag=0;
        for(int i=1; i<=n; i++)
        {
            if(a[i]!=i)
            {
                flag=1;
                break;
            }
        }
        if(flag==0)
        {
            cout<<"0"<<endl;
            continue;
        }
        else
        {
        	int add=1;
            while(1)
            {
                if(add%2!=0)//jishu
                    for(int i=1; i<=n-2; i+=2)
                    {
                        if(a[i]>a[i+1])
                            swap(a[i],a[i+1]);
                    }
                else if(add%2==0)
                    for(int i=2; i<=n-1; i+=2)
                    {
                        if(a[i]>a[i+1])
                            swap(a[i],a[i+1]);
                    }
                flag=0;
                for(int i=1; i<=n; i++)
                {
                    if(a[i]!=i)
                        flag=1;
                }
                if(flag==0)
                {
                    cout<<add<<endl;
                    break;
                }
                add++;
            }
        }
    }
}

B：

题意：
AB两个人打球，不知道谁先发球，一局比赛一定会有输赢，一个人发球赢了就叫守住发球，一个人在他的发球局输了就叫破发球，赢了+1分，输了-1分，给出比分，问有多少个破发球局，列出所有可能情况
思路：
模拟一下就容易找到规律，一个人得分由自己守下来的局和破发对手的局两部分构成，分开计算即可。

//Author:Happy Dog
#include<bits/stdc++.h>
#define ll long long
using namespace std;
set<int> st;
int main()
{
	int t,n,m;
    cin>>t;
    while(t--)
    {
    	int temp;
        st.clear();
        cin>>n>>m;
        if(n<=m) 
		 swap(n,m);
        int a=(n+m)/2,b=(n+m)-a,ans=n-a,add=n-b;
        for(int i=0; i<=m; i++)
        {
            temp=ans+i*2;
            st.insert(temp);
            temp=add+i*2;
            st.insert(temp);            
        }
        cout<<st.size()<<endl;
        for(auto x:st)
        cout<<x<<" ";
        cout<<endl;
    }
}

C：

题意：
也不难：一个人要打怪兽，给定n个洞穴，一个人想杀掉洞穴里的所有怪兽就必须按顺序来杀，每杀一个怪兽就会让这个人的力量+1，杀死怪兽的条件是力量严格大于怪兽的血量，问这个人想杀掉所有怪兽（洞穴选择的顺序可以任意），最小的初始力量为多少。
思路：
首先我们求出来每个洞穴的最小进入力量，对每个怪兽的血量减掉他在山洞里的位置取一个最大值即可，然后算出每个洞穴可为这个人增加的力量，用pair存储，然后排序
如果这个人进入了第i个洞穴，他拥有的力量和获得的力量之和不足以让他进如下一个洞穴，那么他的基准力量就会上升这个差值，最后加上进入第一个洞穴所需要的基础力量就可以了。

//Author:Happy Dog
#include<bits/stdc++.h>
#define ll long long
using namespace std;
pair<ll,ll> p[100009];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
    	ll n;
    	cin>>n;
        for(int i=1; i<=n; i++)
        {
        	ll temp;
            cin>>temp;
            ll tempmax=0,temppmax=0;
            for(int j=1;j<=temp;j++)
            {
            	ll e;
            	cin>>e;
            	if(e-j>tempmax)
            	tempmax=e-j;
			}
			p[i].first=tempmax+2;
			p[i].second=temp;
        }
        sort(p+1,p+1+n);
     /*   for(int i=1;i<=n;i++)
        cout<<p[i].first<<endl;*/
        int ans=p[1].first;
        int now=ans+p[1].second;
        for(int i=2; i<=n; i++)
        {
            if(now>p[i].first)
            {
                now+=p[i].second;
                continue;
            }
            int x=p[i].first-now;
            ans+=x;
            now=p[i].first+p[i].second;
        }
		cout<<ans<<endl;
    }
}

D：

这道题是学长给的思路
有时间了补一下

//Author:Happy Dog
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll dp[4000007];//��
ll sum[4000007];
ll ans[4000007]= {0};
ll t,n,mod;
void solve(int i)
{
    for(int j=1;; j++)
    {
        if(i*j>n)
            return ;
        ans[j*i]=(ans[j*i]+dp[i])%mod;
        if((i+1)*j<=n)
            ans[(i+1)*j]=(ans[(i+1)*j]+mod-dp[i])%mod;
    }
}
int main()
{
    cin>>n>>mod;
    dp[1]=1;
    sum[0]=0;
    for(int i=1; i<=n; i++)
    {
        ans[i]=(ans[i]+(ans[i-1]%mod))%mod;
        if(i!=1)
            dp[i]=(ans[i]+sum[i-1])%mod;
        solve(i);
        sum[i]=(sum[i-1]+dp[i])%mod;
    }
    cout<<dp[n]<<endl;
}