AtCoder Beginner Contest 254（C，D，E，F)
C
这个题是给你一个乱序的数组，你可以把ai和ai+k进行交换，我们需要判断是否可以最后变成从小到大的顺序
那么我们可以想到所有下标对k的余数相同的是可以随便交换，那么我们就把同一个余数就把所有的数按照重新到大的顺序，然后我们再进行判断，如果可以就是yes,否则就是No
#include <algorithm>
#include <iostream>
#include<vector>
#include <string>
#include <set>
using namespace std;
#define int long long
const int maxn=2e5+10;
int a[maxn],ans[maxn];
int n,k;
signed main ()
{
cin>>n>>k;
for (int i=1;i<=n;i++)
{
cin>>a[i];
}
for (int i=0;i<k;i++)
{
vector<int>st;
for (int j=i+1;j<=n;j+=k)
{
st.push_back(a[j]);
}
sort(st.begin(),st.end());
int now=i+1;
for (auto x:st)
{
ans[now]=x;
now+=k;
}
}
bool yes=true;
for (int i=2;i<=n;i++)
{
if (ans[i-1]>ans[i])
{
yes=false;
break;
}
}
if (yes)
{
cout<<"Yes\n";
}
else
{
cout<<"No\n";
}
system ("pause");
return 0;
}
D
这一道题的大意是给你一个n的网格，我们要找到一个点i,j,其中iXj是平方数的个数
对于一个数，我们都可以把一个数x变成prei^iz* prej^k（pre是质数，对于每一个数，都是可以分解成若干个质数），对于是一个平方数，那么那些质数的幂次一定是偶数的
然后我们知道1到nXn一定有1，到n的平方数
那么我们只要列举1到n,记录i的平方时有几种
我们先判断它是否可以分解（质数一定是只有一个，i，i)
然后我们分解x,如果中间的质数出现了奇数次幂，那么我们ans*=pre,那么我们求出的数量就和这个奇数次幂的乘积有关，cnt=sqrt((x-1)/ans),然后我们可以求出1到n的平方数的总个数
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=2e5+10;
#define int long long
int pre[maxn],num[maxn];
int n;
int dp[maxn];
void init(int x)
{
pre[1]=1;
for (int i=2;i<=x;i++)
{
if (pre[i]) continue;
for (int j=i;j<=x;j+=i)
{
pre[j]=i;
}
}
return ;
}
signed main ()
{
cin>>n;
init(n);
int sum=0;
for (int i=1;i<=n;i++)
{
int tmp=0;
if (pre[i]!=i)
{
int x=i,ans=1;
while (pre[x]!=x)
{
int now=pre[x],way=0;
while (pre[x]==now)
{
x/=pre[x];
way++;
}
if (way&1)
{
ans*=now;
}
}
ans*=pre[x];
}
sum+=tmp*2+1;
}
cout<<sum<<'\n';
system ("pause");
return 0;
}
E
这一道题的大意是我们需要建一个图，然后会有q次询问，我们要知道和x之间的距离小于等于k的所有顶点的和
对于这一题题目告诉我们每一个点的度都会小于等于3，那么我们就直接搜索了
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
#define int long long
const int maxn=2e5+10;
vector<int>g[maxn];
int vis[maxn];
int bfs(int n,int k)
{
int ans=0;
queue<pair<int,int>>q;
vector<int>v;
q.push({n,0});
while (!q.empty())
{
int now=q.front().first;
int w=q.front().second;
q.pop();
if (vis[now]) continue;
ans+=now;
v.push_back(now);
vis[now]=1;
if (w==k) continue;
for (int i=0;i<g[now].size();i++)
{
int to=g[now][i];
q.push({to,w+1});
}
}
for (int i=0;i<v.size();i++)
{
vis[v[i]]=0;
}
return ans;
}
signed main ()
{
int n,m;
cin>>n>>m;
for (int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
g[x].push_back(y);
g[y].push_back(x);
}
int q;
cin>>q;
while (q--)
{
int x,k;
cin>>x>>k;
int ans=bfs(x,k);
cout<<ans<<'\n';
}
system ("pause");
return 0;
}
F
这一题大意是给你一个nXn的网格，每一个格子里都有一个数字，每一个i,j的值就是ai+bj.然后我们还是会进行q次询问，每次都会告诉你一个四边形块，我们要知道的是这一块的所有的数的gcd
对于这一题，我们要知道 如果a和b互质，那么a+b和a互质，和b互质，abs(a-b)和a,b也互质
那么gcd(a,b)=gcd(a,abs(a-b))
那么我们对于gcd(ai+bj,ai+bj+1,ai+bj+2)这一行，可以后面的都可以转换成
gcd(ai+bj,bj+1-bj,bj+2-bj+1) 后面的一项减去前面的那一项
对于下一步
我们可以先看到下面,对于这一个网格
| a1+b1 | a1+b2 | a1+b3 | a1+b4 | a1+b5 |
|---|---|---|---|---|
| a2+b1 | a2+b2 | a2+b3 | a2+b4 | a2+b5 |
| a3+b1 | a3+b2 | a3+b3 | a3+b4 | a3+b5 |
| a4+b1 | a4+b2 | a4+b3 | a4+b4 | a4+b5 |
| a5+b1 | a5+b2 | a5+b3 | a5+b4 | a5+b5 |
gcd(ai+b1,ai+b2,ai+b3,ai+b4,ai+b5)变成gcd(ai+b1,b2-b1,b3-b2)，
我们可以发现从1,2到1,5的之间的差值，和2,2和2,5是一样的，
那么我们只要求当i=1的时候，那么我们可以知道 1,2到5,5 这一块的gcd,
但是我们并没有加上a1+bi第一列，
那么我们可以换一个方向
gcd(a1+bi,a2+bi,a3+bi,a4+bi,a5+bi)，同样可以转换成
gcd(a1+bi,a2-a1,a3-a2,a4-a3,a5-a4)
还是当i=1时，我们可以知道 2,1到5,5 这一块的gcd(会有重复的，但是也覆盖了一部分)，但是我们还有一个没有放进去，那就是a1+b1,那我们就自己加进去
我前面表达的可能不太准确，可以看这个大佬，里面有图
然后我们只要求差分的gcd,但是我们怎么求这一段差分的gcd呢
我们这里用了线段树
具体看代码
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;
#define int long long
const int maxn=2e5+10;
int a[2][maxn],d[2][maxn],tr[2][maxn<<2];
void build(int now,int l,int r)
{
if (l==r)
{
tr[0][now]=d[0][l];//0是a的差分，1是b的差分
tr[1][now]=d[1][l];
return ;
}
int mid=(l+r)>>1;
build(now<<1,l,mid);
build(now<<1|1,mid+1,r);
for (int i=0;i<=1;i++)
{
tr[i][now]=__gcd(tr[i][now<<1],tr[i][now<<1|1]);
}
return ;
}
int query(int now,int l,int r,int L,int R,int way)
{
if (L<=l&&r<=R)
{
return tr[way][now];
}
int mid=(l+r)>>1,ans=0;
if (L<=mid)
{
ans=query(now<<1,l,mid,L,R,way);
}
if (R>mid)
{
ans=__gcd(ans,query(now<<1|1,mid+1,r,L,R,way));
}
return ans;
}
signed main ()
{
int n,q;
cin>>n>>q;
for (int i=0;i<=1;i++)
{
for (int j=1;j<=n;j++)
{
cin>>a[i][j];
d[i][j]=abs(a[i][j]-a[i][j-1]);
}
}
build(1,1,n);
while (q--)
{
int h1,h2,w1,w2;
cin>>h1>>h2>>w1>>w2;
int ans=a[0][h1]+a[1][w1];
if (h1!=h2)
{
ans=__gcd(ans,query(1,1,n,h1+1,h2,0));
}
if (w1!=w2)
{
ans=__gcd(ans,query(1,1,n,w1+1,w2,1));
}
cout<<ans<<'\n';
}
system ("pause");
return 0;
}