2022WUSTACM训练赛，感谢Xinima姐姐给的机会捏（）
https://ac.nowcoder.com/acm/contest/38408
A. Ximena的倍数
原题：https://atcoder.jp/contests/abc077/tasks/arc084_b
考虑 num*10%k 和 num+1 两种情况，跑01bfs就可以了。当然最短路也是正解，网上的题解应该都是最短路的。
锐评：这玩意能在洛谷评到紫题纯纯虚高了，绿题蓝题差不多，不过紫题++，好耶。
#include<bits/stdc++.h>
using namespace std;
int k,vis[100005];
deque<pair<int,int>> q;
int main()
{
cin>>k;
q.push_front({1,1});
vis[1]=1;
while(q.size())
{
auto [num,step]=q.front();
q.pop_front();
if(num==0)
{
cout<<step<<endl;
return 0;
}
if(!vis[10*num%k])
{
q.push_front({10*num%k,step});
vis[10*num%k]=1;
}
if(!vis[num+1])
q.push_back({num+1,step+1});
}
return 0;
}B. Ximena与图上难题
原题：https://atcoder.jp/contests/abc224/tasks/abc224_d
一眼搜索了xdm。
每一次只有一个格子是空的，我们记这个格子为第 $i$ 号格子，对于当前状态来说，只有与第 $i$ 个格子有边的才能交换过来，然后嗯跑bfs就可以了。
存图：这题很多人应该是不会存图，讲一下我做题的思路。第一眼，想到了去年新生赛的一个题，是九宫格挪动，那个题好像有个哈希的存图法，但是很浪费。我这题存图的办法是：用一个十进制数字 $mp$ 去存图，对这个十进制数的左起第 $i$ 位，表示第 $i$个格子上站的是几号棋子，空格子我们用0或者9表示都可以。如果用0表示，mp的值域为 $[12345678,876543210]$ ，如果用9表示，值域为 $[123456789,987654321]$ 。而我们都知道 $INT\_MAX=2147483647$ ，所以可以轻松在int范围内表示出我们要的图的状态，用 $map<int,bool>$ 代替数组去实现记录状态的 $vis$ 功能。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=10;
typedef pair<int,int> pii;
int m;
vector<int> G[maxn];
int bg,a[maxn];
map<int,bool> vis;
signed main()
{
cin>>m;
for(int i=0,x,y;i<m;i++)
{
cin>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
for(int i=1,x;i<=8;i++)
{
cin>>x;
a[x]=i;
}
for(int i=1;i<=9;i++)
bg=bg*10+a[i];
queue<pii> q;
q.push({bg,0});
vis[bg]=1;
while(q.size())
{
auto [now,step]=q.front();
q.pop();
if(now==123456780)
{
cout<<step<<endl;
return 0;
}
for(int i=9;i>=1;i--)
{
a[i]=now%10;
now/=10;
}
for(int w=1;w<=9;w++)
{
if(a[w]>0)
continue;
for(auto i:G[w])
{
swap(a[i],a[w]);
int tmp=0;
for(int i=1;i<=9;i++)
tmp=tmp*10+a[i];
if(!vis[tmp])
{
vis[tmp]=1;
q.push({tmp,step+1});
}
swap(a[i],a[w]);
}
}
}
cout<<-1<<endl;
return 0;
}C. Ximena的序列
原题：https://atcoder.jp/contests/abc223/tasks/abc223_d
对每个限制 $a_i$ 向 $b_i$ 连边，然后拓扑排序，要求字典序最小即把queue换成优先队列即可。
挺板的拓扑排序，感觉应该每个人都学一下。
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+7;
int n,m,tot;
int d[maxn];//度数
int ans[maxn];
vector<int> G[maxn];
void toposort()
{
//可以直接存负数，省得写一大段优先队列（懒
// priority_queue<int,vector<int>,greater<int>> q;
priority_queue<int> q;
for(int i=1;i<=n;i++)
if(!d[i])
q.push(-i);
while(q.size())
{
int x=-q.top();
q.pop();
ans[++tot]=x;
for(auto i:G[x])
{
d[i]--;
if(!d[i])
q.push(-i);
}
}
while(q.size())
{
ans[++tot]=-q.top();
q.pop();
}
if(tot==n)
{
for(int i=1;i<=n;i++)
cout<<ans[i]<<" \n"[i==n];
}
else
cout<<-1<<"\n";
}
int main()
{
cin>>n>>m;
while(m--)
{
int x,y;
cin>>x>>y;
d[y]++;
G[x].push_back(y);
}
toposort();
return 0;
}D. 于是，季节更迭，白雪消融。
这题偷个懒，看孙哥的代码吧，有注释
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
#define lowbit(x) (x & (-x))
//#define mid ((l + r) >> 1)
#define int long long
const int INF = 0x3f3f3f3f;
const double PI = acos(-1);
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e6 + 5, maxm = 1e5 + 5, mod = 1e9 + 7;
inline int read()
{
int x = 0, f = 1, ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
f = -f;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
inline int ksm(int x, int y)
{
x %= mod;
int z = 1;
while (y)
{
if (y & 1)
z = z * x % mod;
x = x * x % mod;
y >>= 1;
}
return z;
}
int n, k, p[maxn], pr[maxn], pe[maxn];
// p[i]表示i的最小素因子,pr[i]表示第i个素数
// 素数并不多,第n个素数大概在nlogn级别,所以pr[]数组可以开小一些
// pe[i]表示i的最小素因子的最大幂次值
int f[maxn]; // f[i]表示积性函数在i的取值
inline void get_pre()
{
n = read(), k = read();
p[1] = 1;
int tot = 0;
for (int i = 2; i <= n; i++)
{
if (!p[i])
p[i] = i, pr[++tot] = i, pe[i] = i;
for (int j = 1; j <= tot && pr[j] * i <= n; j++)
{
p[i * pr[j]] = pr[j];
if (p[i] == pr[j]) //如果i的最小素因子等于第j个素数
{
pe[i * pr[j]] = pe[i] * pr[j];
break;
}
else //第j个素数小于i的最小素因子
pe[i * pr[j]] = pr[j];
}
}
ll ans = 1;
f[1] = 1; //积性函数一般f[1]=1(当然等于0也行,就是没啥意义)
for (int i = 2; i <= n; i++)
{
if (i == pe[i]) //处理素数幂的取值
{
f[i] = i / p[i] * (p[i] - 1) * ksm(i, k - 1) % mod;
// 示例2：莫比乌斯函数写法
// f[i] = -(i == p[i]);
// 示例3：因数个数写法
// f[i] = f[i / p[i]] + 1;
// 示例4：因数和写法
// f[i] = f[i / p[i]] + i;
}
else
f[i] = f[i / pe[i]] * f[pe[i]] % mod;
ans += f[i];
}
cout << ans % mod << endl;
}
inline void solve()
{
get_pre();
}
signed main()
{
int t = 1;
// freopen("1.out", "r", stdin);
// t = read();
while (t--)
{
solve();
}
#ifdef sunyuheng365
system("pause");
#endif
}E. Ximena打羽毛球
又是拓扑。
题解from nana:
有M个桶，球有n种颜色，颜色编号为1-n.每种颜色 都有两个球属于同种颜色
我可以进行一个操作就是同时拿两个圆柱体顶上的相同颜色的球，问能否把球全部都拿完。
输入一个n和m
然后每偶数行输入一个k表示该圆柱体内球的个数（最左边代表顶部）
然后奇数行输入k个球的颜色编号
很明显可以想到拓扑排序，例如一个圆柱体1->2->3->4只有1出来后，2才可以出来，2出来后，3才可以
出来...
所以建立单向边即可，最后确定是不是所有颜色都出来的即可。
代码看看别人的，结合一下拓扑板子，这里不赘述。
F. Ximena逛超市
原题：https://atcoder.jp/contests/dp/tasks/dp_q
这个网上的题解写得比我好，不会的可以去看孙哥的代码。
老公！