AtCoder Beginner Contest 290(D,E)

D (思维，数学)

D

这个题的大意就是我们需要标记\(n\)个位置，他是这样标记的，一开始有一个初始值为\(0\)的\(x\)，第一个标记的是\(0\)位置，然后下一步，我们把\(x\)变成\((x+d)mod n\),如果这个位置没有被标记，否则把\(x\)变成\((x+1) mod n\)，这个是没有被标记的，那么标记这个，然后再一次进行加\(d\)进行标记，直到所有的位置都被标记，问第\(k\)个被标记的位置是哪一个

我不知道怎么说，感觉有点想找规律，我在自己出了几组数据后面发现了一点点的规律，但是还有一个很重要的点不知道

对于这一个题

它一定有一个循环，不管\(k\)是大还是小

我们可以把一个长度为\(n\)的位置分成\(\frac{n}{gcd}\)段（\(gcd\)是\(n\)和\(d\)段）

假如有三段

第一步在第一段的第一个位置，第二步，在第二段的第一个位置，第三步在第三段的第一个，那么第四步我们又会回答第一段的第一个位置，但是这个位置已经被标记，所以，来到第一段的第二个位置，后面的五六步分别在第二段和第三段的第二个位置

所以，我们可以首先求出这个\(n\)可以被\(d\)分成多少段，\(\frac{n}{gcd}\)

然后我们判断这一个\(k\)在第几段，就可以知道位置的一部分，我们知道第一段里面有\(0\),第二段里面是\(0+\frac{n}{gcd}\),他们相邻之间的距离均为\(\frac{n}{gcd}\),所以，同一段的位置对\(\frac{n}{gcd}\)取余是一样的，然后我们又观察到第一段取余为\(0\),后面依次递增。

可以由\((k-1)\times d mod \frac{n}{gcd}\),得到

但是我们发现这只是大致知道它在那一段，而不知道它经历了多少次循环（第一次是在原来的位置，后面出现了重复的位置，会依次往后面走）

那我们可以判断它进行了所少次循环，可以直接除\(\frac{n}{gcd}\)

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <stack>
#include<cmath>
#include <unordered_map>
#include <array>
#include <cstring>
using namespace std;
#define int long long 
#define LL long long
#define ios  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define inf 1e18
#define INF 1e18
#define mem(a,b) memset((a),(b),sizeof(a))
const int maxn=2e5+10;
const int mod=1e9+7;
int n,d,k;
void solve()
{
    cin>>n>>d>>k;
    k--;
    int gcd=__gcd(n,d);
    n/=gcd;
    int cnt=k%n;
    int add=k/n;
    n=n*gcd;
    int ans=(cnt*d)%n+add;
    cout<<ans<<"\n";
    return ;
}
signed main ()
{
    int t=1;
     cin>>t;
    while (t--)
    {
        solve();
    }
    system ("pause");
    return 0;
}

E(思维)

E

题意大意给出一个数组，问我们如果任意选择一对\(l,r\),要把这个一段变成回文的话，需要最少改变多少个数字

问对于任意组合的\(l,r\)的最少的和

我看到了一个很简单的解法

由于这是一个回文，这个回文如果再在这个回文的基础上往左右两边添加，那么对于最新的\(l,r\)所需的操作对于这一个端点位置，如果需要改变就一定要改变，但是对于和端点位置所在的一个回文串，他们的变化就是上一次更新的操作数

所以我们只需要从中间往两边遍历，然后每一次我们只需要加上这一个位置需要改变的操作，但是每一次求出的操作数可能会被后面用到

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <stack>
#include<cmath>
#include <unordered_map>
#include <array>
#include <cstring>
using namespace std;
#define int long long 
#define LL long long
#define ios  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define inf 1e18
#define INF 1e18
#define mem(a,b) memset((a),(b),sizeof(a))
const int maxn=2e5+10;
const int mod=1e9+7;
int n,cnt[maxn],a[maxn];
void solve()
{
    cin>>n;
    int sum=0;
    int ans=0;
    for (int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    int cur=0;
    for (int i=(n+1)/2;i>=1;i--)
    {
        int l=i,r=n-l+1;
        sum+=cur-cnt[a[l]];
        cnt[a[l]]++;
        cur++;
        if(l!=r)
        {
            sum+=cur-cnt[a[r]];+
            cnt[a[r]]++;
            cur++;
        }
        ans+=sum;
    }
    cout<<ans<<"\n";
    return ;
}
signed main ()
{
   int t=1;
    while (t--)
    {
        solve();
    }
    system ("pause");
    return 0;
}