AtCoder Beginner Contest 290(D,E)
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(思维)
题意大意给出一个数组,问我们如果任意选择一对\(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;
}
- Beginner AtCoder Contest 290beginner atcoder contest 290 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 315 beginner atcoder contest 334