我是傻逼，赛后D题加了一行就过了。。。
A.Distinct Digits
题意
给出 $l,r(\le 10^5)$ ，求 $x\in [l,r]$ ，要求 $x$ 各数位均不同。
题解
数据范围小，直接暴力判断。
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
char ch=getchar(); int f=1,x=0;
while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
return f*x;
}
int l,r,cur[10];
inline bool check(int x)
{
int j=0;
while (x)
{
cur[++j]=x%10;
x/=10;
for (int k=1;k<j;k++) if (cur[j]==cur[k]) return 0;
}
return 1;
}
signed main()
{
l=read(); r=read();
for (int i=l;i<=r;i++)
{
if (check(i))
{
printf("%d",i);
return 0;
}
}
return 0&puts("-1");
}B.Filling the Grid
题意
有个 $n\times m(n,m\le 1000)$ 的矩形，每个格子可以被涂成黑/白两色。给出两个数组 $r$ 和 $c$ ，$r_i$ 表示从第 $i$ 行第 $1$ 列开始有连续多少个黑色格子，$c_i$ 表示第 $i$ 列第 $1$ 行开始。问满足 $r,c$ 的涂色方案有多少种。
题解
按题意膜你，对于每一行，前 $r_i$ 个涂成黑色，第 $r_i+1$ 个涂成白色。列同理，不过涂的时候需要判断一下是否矛盾。最后如果还剩 $x$ 个格子没涂那答案就是 $2^x$ 。
#include<bits/stdc++.h>
#define ha 1000000007
using namespace std;
inline int read()
{
char ch=getchar(); int f=1,x=0;
while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
return f*x;
}
int n,m,r[1005],c[1005],mp[1005][1005];
signed main()
{
memset(mp,-1,sizeof(mp));
n=read(); m=read();
for (int i=1;i<=n;i++)
{
r[i]=read();
for (int j=1;j<=r[i];j++) mp[i][j]=1;
mp[i][r[i]+1]=0;
}
for (int i=1;i<=m;i++)
{
c[i]=read();
for (int j=1;j<=c[i];j++)
{
if (mp[j][i]==0) return 0&puts("0"); //矛盾
mp[j][i]=1;
}
if (mp[c[i]+1][i]==1) return 0&puts("0");
mp[c[i]+1][i]=0;
}
int ans=1;
for (int i=1;i<=n;i++) for (int j=1;j<=m;j++)
{
if (mp[i][j]!=-1) continue;
ans=ans*2%ha;
}
printf("%d",ans);
return 0;
}C.Primes and Multiplication
题意
题解
可以发现答案就是
$$\prod \forall prime(x)^{\sum_{i=1}^n \frac{i}{prime(x)} \ (i\equiv 0\pmod {prime(x)})}$$
计算 $\sum_{i=1}^n \frac{i}{prime(x)} \ (i\equiv 0\pmod {prime(x)})$ 可以让 $n$ 不断的除 $prime(x)$ ，将商累加起来。
#include<bits/stdc++.h>
#define ll long long
#define ha 1000000007
using namespace std;
inline ll read()
{
char ch=getchar(); ll f=1,x=0;
while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
return f*x;
}
bool ss[100005];
ll x,n,cnt,ans=1,zs[100005],c[100005],ccnt;
inline void getPrime()
{
memset(ss,1,sizeof(ss));
ss[0]=ss[1]=0;
for (ll i=2;i*i<=x;i++)
{
if (ss[i]) zs[++cnt]=i;
for (ll j=1;j<=cnt && zs[j]*i*zs[j]*i<=x;j++)
{
ss[zs[j]*i]=0;
if (i%zs[j]==0) break;
}
}
}
inline ll qpow(ll x,ll y)
{
ll ans=1;
while (y)
{
if (y&1) ans=ans*x%ha;
y>>=1;
x=x*x%ha;
}
return ans;
}
signed main()
{
x=read(); n=read();
getPrime();
for (ll i=1;i<=cnt;i++)
{
if (x%zs[i]) continue;
c[++ccnt]=zs[i]; //分解质数
while (x%zs[i]==0) x/=zs[i];
}
if (x>1) c[++ccnt]=x;
for (ll i=1;i<=ccnt;i++)
{
ll n2=n,cur=0;
while (n2) cur+=n2/=c[i]; //不断除当前质数
ans=ans*qpow(c[i],cur)%ha;
}
printf("%lld",ans);
return 0;
}D.Complete Tripartite
题意
题解
可以发现不与 $x$ 直接相连的点一定和 $x$ 在同一集合。
那么就可以先把 $1$ 归到集合 $\text{①}$ ，然后遍历所有与 $1$ 相连的点，把他们标为集合 $\text{②}$ 。剩下的没有被标成 $\text{②}$ 的就一定在 $\text{①}$ 里。
再随便选一个 $\text{②}$ 中的节点，把与它相连且 $\notin \text{①}$ 的节点标成 $\text{③}$ 。
至此集合就划分完了，接下来只需要验证是否满足题意。
- 如果三种集合有一种的节点个数 $cnt[i]$ 为 $0$ ，那么无解。（
我就是因为这个炸掉了） - 对于节点 $x$ ，遍历所有与它相连的节点 ，并记录三种集合的个数 $cur[i]$。如果 $x$ 所属的集合个数不为 $0$ ，或者其它集合的 $cnt[i]\neq cur[i]$ ，那么无解。
#include<bits/stdc++.h>
#define ha 1000000007
using namespace std;
inline int read()
{
char ch=getchar(); int f=1,x=0;
while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
return f*x;
}
struct Edge {
int next,to;
} edge[600005];
bool vis[100005];
int cnt,head[100005],n,m,a,b,col[100005],cnt2[4],cur[4];
inline void add(int u,int v)
{
edge[++cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt;
}
signed main()
{
n=read(); m=read();
for (int i=1;i<=m;i++)
{
a=read(); b=read();
add(a,b);
add(b,a);
}
col[1]=1; cnt2[1]=1;
for (int i=head[1];i;i=edge[i].next) //从 1 开始，标记集合 ②
{
int y=edge[i].to;
col[y]=2;
}
for (int i=1;i<=n;i++) if (!col[i]) col[i]=1,cnt2[1]++; //剩下的在 ①
int st=2;
for (;st<=n && col[st]!=2;st++); //找到一个 ② 中的节点
for (int i=head[st];i;i=edge[i].next) //标记集合 ③
{
int y=edge[i].to;
if (col[y]==1) continue;
col[y]=3;
cnt2[3]++;
}
cnt2[2]=n-cnt2[1]-cnt2[3];
if (!cnt2[1] || !cnt2[2] || !cnt2[3]) return 0&puts("-1"); //无解情况 1
for (int x=1;x<=n;x++)
{
memset(cur,0,sizeof(cur));
for (int i=head[x];i;i=edge[i].next)
{
int y=edge[i].to;
cur[col[y]]++;
}
for (int i=1;i<=3;i++)
{
if (col[x]==i && cur[i]) return 0&puts("-1");
else if (col[x]!=i && cnt2[i]!=cur[i]) return 0&puts("-1"); //无解情况 2
}
}
for (int i=1;i<=n;i++) printf("%d ",col[i]);
return 0;
}