ARC149
A
直接记录\(1111..\)然后\(check\)一下即可
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
int n;
int m;
int Mtl[MAXN];
signed main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
{
Mtl[i]=((long long)Mtl[i-1]*10+1)%m;
}
for(int len=n;len>=1;len--)
{
for(int x=9;x>=1;x--)
{
if(((long long)Mtl[len]*x)%m==0)
{
for(int i=1;i<=len;i++)
{
printf("%d",x);
}
return 0;
}
}
}
printf("-1");
}
B
捆绑着任意排序
我猜最大值是\(A\)排序\(B\)乱序/\(B\)排序\(A\)乱序
证明的话考虑调整法,如果\(A\)有一个数不在\(LIS\)里就把它插进去,这样一定不劣
#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e5+5;
struct node{
int A,B;
}a[MAXN];
bool cmp(node x,node y)
{
return x.A<y.A;
}
bool kmp(node x,node y)
{
return x.B<y.B;
}
int n;
int Bit[MAXN];
int lowbit(int x)
{
return x&(-x);
}
void update(int k,int x)
{
for(int i=k;i<=n;i+=lowbit(i))
{
Bit[i]=max(Bit[i],x);
}
}
int Q(int k)
{
int res=0;
for(int i=k;i>=1;i-=lowbit(i))
{
res=max(res,Bit[i]);
}
return res;
}
signed main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i].A);
}
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i].B);
}
sort(a+1,a+1+n,cmp);
int Res=0;
for(int i=1;i<=n;i++)
{
int kp=Q(a[i].B)+1;
Res=max(Res,kp+n);
update(a[i].B,kp);
}
memset(Bit,0,sizeof(Bit));
sort(a+1,a+1+n,kmp);
for(int i=1;i<=n;i++)
{
int kp=Q(a[i].A)+1;
Res=max(Res,kp+n);
update(a[i].A,kp);
}
printf("%d\n",Res);
}
C
偶数前半部分一起,奇数放后半部分
交接处偶数满足\(\bmod 3=2\),奇数满足\(\bmod 3=1\)
这样\(n\ge 6\)可以满足
剩下的特判即可
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+5;
int n;
int vis[MAXN];
bool Ck(int x)
{
for(int i=2;i*i<=x;i++)
{
if(x%i==0)
{
return 1;
}
}
return 0;
}
signed main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d",&n);
if(n==3)
{
printf("5 3 1\n");
printf("9 7 8\n");
printf("6 2 4\n");
return 0;
}
vector<int>Odd;
vector<int>Even;
vector<int>odd;
vector<int>even;
for(int i=1;i<=n*n;i++)
{
if(i&1)
{
if(i%3==1)
{
Odd.push_back(i);
}
}
else
{
if(i%3==2)
{
Even.push_back(i);
}
}
}
int Mt=min(Even.size(),Odd.size());
Mt=min(Mt,n);
for(int i=0;i<Mt;i++)
{
vis[Odd[i]]=1;
}
for(int i=0;i<Mt;i++)
{
vis[Even[i]]=1;
}
while(Even.size()>Mt)
{
Even.pop_back();
}
while(Odd.size()>Mt)
{
Odd.pop_back();
}
reverse(Odd.begin(),Odd.end());
if(Mt!=n)
{
//cerr<<"fuck"<<endl;
for(int i=1;i<=n*n;i+=2)
{
for(int j=2;j<=n*n;j+=2)
{
if(Odd.size()==n)
{
break;
}
if(vis[i])
{
continue;
}
if(vis[j])
{
continue;
}
if(Ck(i+j))
{
Odd.push_back(i);
vis[i]=1;
Even.push_back(j);
vis[j]=1;
}
}
}
//cerr<<"fuck"<<endl;
}
for(int i=1;i<=n*n;i++)
{
if(i&1)
{
if(vis[i])
{
continue;
}
odd.push_back(i);
}
else
{
if(vis[i])
{
continue;
}
even.push_back(i);
}
}
if(n&1)
{
for(int i=1;i<=n/2;i++)
{
for(int j=1;j<=n;j++)
{
if(even.empty())
{
break;
}
printf("%d ",even.back());
even.pop_back();
}
if(even.empty())
{
for(int j=n/2+1;j<=n;j++)
{
printf("%d ",Even[j-n/2-1]);
}
}
printf("\n");
}
for(int i=1;i<=n/2;i++)
{
printf("%d ",Even[i+n/2]);
}
for(int i=n/2+1;i<=n;i++)
{
printf("%d ",Odd[i-n/2-1]);
}
printf("\n");
for(int i=1;i<=n/2;i++)
{
for(int j=1;j<=n;j++)
{
if(i==1&&j<=(n/2))
{
printf("%d ",Odd[j+n/2]);
}
else
{
printf("%d ",odd.back());
odd.pop_back();
}
}
printf("\n");
}
}
else
{
//cerr<<Odd.size()<<' '<<Even.size()<<endl;
for(int i=1;i<n/2;i++)
{
for(int j=1;j<=n;j++)
{
printf("%d ",even.back());
even.pop_back();
}
printf("\n");
}
for(int i=0;i<n;i++)
{
printf("%d ",Even[i]);
}
printf("\n");
for(int i=0;i<n;i++)
{
printf("%d ",Odd[i]);
}
printf("\n");
for(int i=1;i<n/2;i++)
{
for(int j=1;j<=n;j++)
{
printf("%d ",odd.back());
odd.pop_back();
}
printf("\n");
}
}
}
D
DJNB！！
考虑这个过程\([-D_i,D_i]\)这个区间的数相当于是直接交换
\([-\infin,-D_i],[D_i,\infin]\)平移一下
这样处理很麻烦
考虑\([-D_i,0),(0,D_i]\)是对称的,值也是相反数关系,我们可以直接删除\([-D_i,0)\)用带权并查集维护
这样我们就可以直接平移原点了,删除原点左边/右边的数并合并即可
// LUOGU_RID: 119069522
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e6+5;
const int MAXM=2e6+5;
int m;
int n;
int X[MAXN];
int D[MAXN];
int L[MAXM];
int fa[MAXM];
int dep[MAXM];
int find(int x)
{
if(fa[x]==x)
{
return fa[x];
}
int s=fa[x];
fa[x]=find(fa[x]);
dep[x]=dep[s]^dep[x];
return fa[x];
}
void unionn(int i,int j)
{
int ex=find(i);
int ey=find(j);
fa[ex]=ey;
dep[ex]=(dep[j]^dep[i]^1);
}
pair<int,int>Ans[MAXM];
signed main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&X[i]);
L[X[i]]=i;
Ans[i].first=0;
}
for(int i=1;i<=m;i++)
{
scanf("%d",&D[i]);
}
int Pi=0;
int l=1;
int r=1e6;
for(int i=l;i<=r;i++)
{
fa[i]=i;
dep[i]=0;
}
for(int i=1;i<=m;i++)
{
if(Pi>r)
{
Pi-=D[i];
if(Pi<=1e6&&Pi>0&&(!Ans[Pi].first))
{
Ans[Pi].first=1;
Ans[Pi].second=i;
}
if(Pi>=l&&Pi<=r)
{
if(Pi-l>r-Pi)
{
for(int i=Pi+1;i<=r;i++)
{
int To=2*Pi-i;
unionn(i,To);
}
r=Pi-1;
}
else
{
for(int i=l;i<=Pi-1;i++)
{
int To=2*Pi-i;
unionn(i,To);
}
l=Pi+1;
}
}
}
else if(Pi<l)
{
Pi+=D[i];
if(Pi<=1e6&&Pi>0&&(!Ans[Pi].first))
{
Ans[Pi].first=1;
Ans[Pi].second=i;
}
if(Pi>=l&&Pi<=r)
{
if(Pi-l>r-Pi)
{
for(int i=Pi+1;i<=r;i++)
{
int To=2*Pi-i;
unionn(i,To);
}
r=Pi-1;
}
else
{
for(int i=l;i<=Pi-1;i++)
{
int To=2*Pi-i;
unionn(i,To);
}
l=Pi+1;
}
}
}
//printf("%d %d??\n",)
}
for(int i=1;i<=n;i++)
{
//printf("%d %d\n",X[i],find(X[i]));
if(Ans[find(X[i])].first)
{
printf("Yes %d\n",Ans[find(X[i])].second);
}////
else
{
int Gk=find(X[i])-Pi;
// if(i==n)
// {
// printf("%d????\n",dep[X[i]]);
// }
if(dep[X[i]])
{
Gk*=-1;
}
printf("No %d\n",Gk);
}
}
}