Codeforces981(Div3 A-F)

A. Sakurako and Kosuke

题目链接:https://codeforces.com/contest/2033/problem/A

樱子和浩介决定在坐标线上玩一些游戏。当前点的位置在 x=0。他们将轮流进行，而 樱子将是第一个开始的人。

在第 i 次移动中，当前玩家将把点移动 2⋅i−1 个单位。樱子总是将点向负方向移动，而浩介总是向正方向移动。

换句话说，以下情况将发生：

• 1.樱子将把点的位置改变 −1,现在是 x=−1
• 2.浩介将把点的位置改变 3,现在是 x=2
• 3.樱子将把点的位置改变 −5,现在是 x=−3
• ⋯⋯

他们将继续游戏，直到点的坐标的绝对值不超过 n。更正式地说，游戏在 −n≤x≤n 时继续。可以证明游戏总会结束。

你的任务是确定谁将是最后一个出手的人。

输入

第一行包含一个整数 t (1≤t≤100) — 樱子和浩介玩的游戏数量。

每个游戏由一个数字 n (1≤n≤100) — 定义游戏结束条件的数字描述。

输出

对于每个 t 个游戏，输出一行该游戏的结果。如果樱子是最后一个出手的人，输出 “樱子”（不带引号）；否则输出 “浩介”。

思路：直接模拟即可，我们维护一个当前位置，当超过正负n时退出即可，但是注意n最大为100，我记得当i == 101时才会超出

void solve()
{
    int n;
    cin>>n;
    int sen = 0;
    for(int i = 1;i <= 300;i++)
    {
        if(i % 2) sen -= (i * 2 - 1);
        else sen += (i * 2 - 1);

        if(abs(sen) > n)
        {
            if(i % 2) cout<<"Sakurako\n";
            else cout<<"Kosuke\n";

            return;
        }
    }
}

B. Sakurako and Water

​
题目链接:https://codeforces.com/contest/2033/problem/B

​在与光介的旅程中，咲良子和光介发现了一个可以表示为大小为 n×n 的矩阵的山谷，其中在 i 行和 j 列的交点上有一座高度为 a[i][j]​ 的山。

如果 a[i][j]<0，那么那里就有一个湖。

光介非常害怕水，所以咲良子需要帮助他：

她可以用魔法选择一个方形的山脉区域，并将该区域主对角线上的每座山的高度增加一个单位。

更正式地说，她可以选择一个子矩阵，其左上角位于 (i,j)，右下角位于 (p,q)，使得 p−i=q−j。

然后，她可以将每个位于 (i+k) 行和 (j+k) 列交点的元素加一，对于所有 k 使得 0≤k≤p−i。

确定咲良子必须使用魔法的最小次数，以确保没有湖泊。

思路：这个题最开始题目描述写的依托，看半天读不懂，后来改了题面。

大概就是我们可以选择一个正方形，每次操作只能把这个正方形的主对角线加1。

因为是只能取正方形主对角线，所以我们直接从整个矩阵的左下角往右上角取，或者反过来也行，

记录一下每条对角线的最小值，加到答案即可。

void XJT___solve()
{
    int n;
    cin>>n;

    vector<vector<int>>v(n + 1,vector<int>(n + 1));
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= n;j++) cin>>v[i][j];

    int x = n;
    int ans = 0;
    while(true)
    {
        int mi = INF;
        int y = 1;
        for(int i = x;i <= n;i++) 
        {
            mi = min(mi,v[i][y]);
            y++;
        }
        
        if(mi < 0) ans += abs(mi);

        x--;
        if(x < 1) break;
    }

    x = n - 1;
    while(true)
    {
        int mi = INF;
        int y = n;
        for(int i = x;i >= 1;i--)
        {
            mi = min(mi,v[i][y]);
            y--;
        }

        if(mi < 0) ans += abs(mi);

        x--;
        if(x < 1) break;
    }

    cout<<ans<<'\n';
}

C. Sakurako’s Field Trip

​
题目链接:https://codeforces.com/contest/2033/problem/C

即使在大学，学生们也需要放松。这就是为什么樱子老师决定进行一次实地考察。已知所有学生将排成一行。

索引为 i 的学生有一个感兴趣的话题，描述为 ai​。作为老师，您希望最小化学生队列的 干扰。

队列的 干扰 定义为有相同感兴趣话题的相邻人数。换句话说，干扰 是满足 a[j]​=a[j]+1​ 的索引 j(1≤j<n) 的数量。

为了做到这一点，您可以选择索引 i (1≤i≤n) 并交换位置 i 和 n−i+1 的学生。您可以进行任意次数的交换。

您的任务是确定通过上述操作可以达到的最小 干扰 量。

思路:最吃屎的一道题，卡了很久，后来发现直接贪心当前位置和前一个位置的即可。

对于 i 和 i - 1以及所对应的交换位置 n - i + 1 和 n - i + 2 我们去判断一下交换是否更优，如果更优就交换。

下面代码是看的别人的自己重新写了一遍然后加了几个注释(自己写的那个感觉太丑)
​

void solve()
{
    int n;
    cin>>n;
    vector<int>v(n + 1);
    for(int i = 1;i <= n;i++) cin>>v[i];

    for(int i = 1;i <= (n / 2);i++)
    {
        int x1 = v[i - 1], y1 = v[n - i + 2];
        int x2 = v[i], y2 = v[n - i + 1];

        int res1 = (x1 == x2) + (y1 == y2); // 不换位置
        int res2 = (x1 == y2) + (y1 == x2); // 换位置

        // 如果换位置更优则交换
        // 不能比较后边的，因为如果比较v[i + 1],那么当i == i + 1时，如果此时交换了会影响到v[i].
        // 如果非要比较i和i + 1,就得从里面往外边遍历.
        if(res1 > res2) swap(v[i], v[n - i + 1]);
    }

    int ans = 0;
    for(int i = 1;i <= n;i++) if(v[i] == v[i - 1]) ans++;

    cout<<ans<<'\n';
}

D. Kousuke’s Assignment

题目链接:https://codeforces.com/contest/2033/problem/D

在与樱子的一次旅行后，浩介非常害怕，因为他忘记了他的编程作业。

在这个作业中，老师给了他一个包含 n 个整数的数组 a，并要求他计算数组 a 中的 不重叠 段的数量，使得每个段被认为是 美丽的。

如果段 [l,r] 满足 a[l]​+a[l+1]​+⋯+a[r−1]​+a[r]​=0，则该段被认为是 美丽的。

对于固定的数组 a，你的任务是计算最大的不重叠 美丽 段的数量。

思路:听说是道很典的题(我的题做的还是太少了)，我们直接用map记录那些出现过的数，每次匹配到后清空map即可;

但是注意某个数为0的时候一定是最优的，我们可以单独拿出来(如果不太理解可以手动模拟几个样例应该就能明白)

还有就是cf不要用unordered_map。。。

void solve()
{
    int n;
    cin>>n;
    vector<ll>v(n);
    for(int i = 0;i < n;i++) cin>>v[i];

    int cnt = 0;
    map<ll,int>mp;
    ll sum = 0;

    for(int i = 0;i < n;i++)
    {
        sum += v[i];
        if(mp.find(sum) != mp.end() || sum == 0) 
        {
            cnt++;
            sum = 0;
            mp.clear();
        }

        mp[sum]++;
    }

    cout<<cnt<<'\n';    
}

E. Sakurako, Kosuke, and the Permutation

题目链接:https://codeforces.com/contest/2033/problem/E

佐仓子的考试结束了，她表现得非常出色。作为奖励，她收到了一个排列 p。光介并不完全满意，因为他未通过一门考试，没有收到礼物。

他决定偷偷溜进她的房间（多亏了她锁的密码）并破坏这个排列，使其变得 简单。

一个排列 p 被认为是 简单 的，如果对于每个 i (1≤i≤n)，以下条件之一成立：

• p[i]=i
• p[p[i]]=i

例如，排列 [1,2,3,4]、[5,2,4,3,1] 和 [2,1] 是 简单 的，而 [2,3,1] 和 [5,2,1,4,3] 不是。

在一次操作中，光介可以选择索引 i,j (1≤i,j≤n) 并交换元素 p[i]​ 和 p[j]​。

佐仓子即将回家。你的任务是计算光介需要执行的最小操作次数，以使排列变得简单。

思路:题意是对于那个排列每一个位置的数都需要满足上面条件的其中一个，听说也是一道很典的题;

我们直接暴力找环，然后对答案的贡献就是这个环的个数减一除二 ((cnt - 1) / 2)。

不会证明，但是模拟了样例之后发现就是这个。

还有一种思路是我们可以开两个数组，一个存 下标->值，一个存 值->下标，然后跑一遍，如果不满足就交换两个数组的值。

下面是找环的代码

void solve()
{
    int n;
    cin>>n;
    vector<int>v(n + 1);
    for(int i = 0;i < n;i++) cin>>v[i];

    vector<int>st(n,0);
    int ans = 0;

    for(int i = 0;i < n;i++)
    {
        if(st[i] == 0)
        {
            int j = i;
            int sen = 0;

            while(st[j] == 0)
            {
                st[j] = 1;
                j = v[j] - 1;
                sen++;
            }

            ans += (sen - 1) / 2;
        }
    }

    cout<<ans<<'\n';
}

​

F. Kosuke’s Sloth

题目链接:https://codeforces.com/contest/2033/problem/F

小笠原太懒了。他不会给你任何说明，只给你任务：

斐波那契数列定义如下：

• f(1)=f(2)=1.
• f(n)=f(n−1)+f(n−2) (3≤n)

我们用 G(n,k) 表示第 n 个可被 k 整除的斐波那契数的索引。给定 n 和 k，计算 G(n,k)。

由于这个数字可能太大，请输出它对 1e9+7 取模的结果。

例如：G(3,2)=9 因为第 3 个可被 2 整除的斐波那契数是 34。 [1,1,2,3,5,8,13,21,34]。

输入
输入数据的第一行包含一个整数 t (1≤t≤1e4) — 测试用例的数量。

第一行也是唯一一行包含两个整数 n 和 k (1≤n≤1e18, 1≤k≤1e5)。

保证所有测试用例中 k 的总和不超过 1e6。

输出
对于每个测试用例，输出唯一的数字：值 G(n,k) 对 109+7 取模的结果。

思路:其实简单看题后我们就能发现，本题的解法就是在斐波那契数列中找到第一个能被k整除的数然后乘以n就行了。但是问题在于如何找到这个数。一个很直接的想法，我们直接暴力枚举不就好了？但是问题又来了，我们怎么知道是否能在时间范围内枚举到第一个被k整除的数？

一个数学结论:斐波那契数列在模p的条件下,他的循环节最大不会超过6p

这是大佬的证明:https://www.cnblogs.com/wlzhouzhuan/p/13901190.html

在本题下，k最大为1e5,也就是说在理论最坏情况下会跑 6e5的样子，不算很大的数，所以我们就可以直接枚举了。

​

const int N = 1e6 + 10;
ll fib[N];

void solve()
{
    ll n,k;
    cin>>n>>k;

    fib[1] = 1,fib[2] = 1;

    int sign = 3;
    while(true)
    {
        fib[sign] = (fib[sign - 1] + fib[sign - 2]) % k;
        
        if(!fib[sign]) break;

        sign++;
    }

    if(k == 1) sign = 1;

    cout<<(n % mod) * sign % mod<<'\n';
}

G. Sakurako and Chefir

题目链接:https://codeforces.com/contest/2033/problem/G