题意：01序列，每次可以选择\(x_i\)，\(y_i\)使得这两个位置有序，求一种方法使得除了该序列之外的其他序列均可排有序的方法
思路：首先，需要完全排好任意随机数组需要\(\frac{n(n-1)}{2}\)次交换，因此少一个就需要\(\frac{n(n-1)}{2}-1\)次交换，我们需要将所有的1标记出来，那么我们将最前面的1尝试交换到后面的所有1位置，然后从后往前进行插入排序，但除了第一个1的位置不往后放，最后让这个1的位置插入排序到它的目标位置前的所有位置即可
#include<bits/stdc++.h>
using namespace std;
#define debug(x) cout << #x << " = " << x << endl;
const int N = 17;
bool a[N];
int main(){
int t;cin >> t;
while(t--){
int n;cin >> n;
cout << n*(n - 1) / 2 - 1 << endl;//数量肯定少一个
string s;cin >> s;
int be = 0,num = 0;
for(int i = 1;i <= n;i++){
a[i] = s[i - 1] - '0';
if(a[i] && !be){//找第一个1
be = i;
}
if(a[i])//记录1的总数量
num++;
}
for(int i = be + 1;i <= n;i++)//第一个1与所有1尝试交换
if(a[i])
cout << be << ' ' << i << endl;
for(int i = n;i >= 1;i--){
for(int j = 1;j < i;j++){
if(j != be){
cout << j << ' ' << i << endl;
}
}
}
for(int i = n - num;i > be;i--){
cout << be << ' ' << i << endl;
}
}
}
题意：\(n×m\)的矩阵，每次选一个点\((x_i,y_i)\)吃掉所有\(x\leq x_i\&y\leq y_i\)的所有点，每次至少吃一个，吃掉最后一个的败，问先手胜还是败
思路：\(1×1\)矩阵必败，除它之外情况下假设选取\((1,1)\)败，那么我们可以选取那个能够让先手败的第二步取法从而胜利(啊？这样证明?)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
int n,m;cin >> n >> m;
if(n == 1 && m == 1)
cout << "Walk Alone";
else
cout << "Kelin";
}
题意：交换b序列的一对元素使得\(\sum^{n}_{i=1}|a_i-b_i|\)最小
思路：只有相交的段，并且方向相反的能减少，减少大小为相交长度的两倍
![Matches]()
那么给所有线段排序并给出类型维护两种即可
#include<bits/stdc++.h>
using namespace std;
#define debut(x) cout << ＃ｘ ＜＜ ＂ ＝ ＂ ＜＜ ｘ ＜＜ endl;
#define ll long long
const int N = 1e6 + 10,inf = 1e9 + 10;
ll a[N],b[N];
signed main(){
int n;cin >> n;
vector<array<ll,3>> seg(n,{0,0,0});
ll ans = 0;
for(int i = 1;i <= n;i++)
cin >> a[i];
for(int i = 1;i <= n;i++)
cin >> b[i];
for(int i = 1;i <= n;i++){
if(a[i] > b[i])
seg[i - 1] = {b[i],a[i],0};
else
seg[i - 1] = {a[i],b[i],1};
ans += abs(a[i] - b[i]);
}
sort(seg.begin(),seg.end());
ll mx[2] = {-inf,-inf},ma = 0;
for(array<ll,3> tem : seg){
mx[tem[2]] = max(tem[1],mx[tem[2]]);
ma = max(ma,min(mx[tem[2]^1],tem[1]) - tem[0]);
}
cout << ans - 2*ma << endl;
}
题意：从1元开始赌，失败加倍，胜利赢赌注的两倍，问从n确切赢到n+m的概率，如果比n+m多则不继续
思路：失败加倍，那么就相当于二进制位均为1，胜利赢两倍，也就是最高二进制位高1的一个数，两者相减为一大轮赢的钱数，一定为1，因此要从n赢到n+m就必须赢m把，然后当数量在\(2^k-1\)到\(2^{k+1}-2\)之间允许失败\(k-1\)次，因此赢的概率为\(1-\frac{1}{2^k}\)即不能连续输\(k\)轮
#include<bits/stdc++.h>
using namespace std;
#define debut(x) cout << #x << " = " << x << endl;
#define ll long long
const int p = 998244353;
ll qpow(ll x,ll y){
ll ans = 1;
while(y){
if(y&1) ans = (ans * x) % p;
x = (x*x) % p;
y >>= 1;
}
return ans;
}
signed main(){
ll n,m;cin >> n >> m;
ll k = 0,aim = n + m - 1,ans = 1;
while(n > ((ll)1 << (k + 1)) - 2)
k++;
ll _2 = qpow(2,p - 2);
while(n <= aim){
ll num = min(aim,((ll)1 << (k + 1)) - 2) - n + 1;
ans = ans * (qpow(1 + p - qpow(_2,k),num)) % p;
n = ((ll)1 << ++k) - 1;
}
cout << ans << endl;
}
题意：给一张图，可以将任意边替换成长度为2的边，并且正中间有一个点，与点1距离小于等于k的最大点数量
思路：对于每个点来说，这样一条边使它得到最小的距离即可，其他边均可任意加点，因此先跑一遍bfs得到距离，然后枚举所有边，如果距离刚好为+1，那么标记较远的点，下次再读到较远点标记过时就让这条边任意加点
最后还需要考虑叶子节点，那么如果该节点只要一条边相连并且被标记过，并且距离小于k，那么那一条边就可以加上k-dis个点让它的距离变成k
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 10;
int dis[N];
bool vis[N],use[N];
pair<int,int> edge[N*2];
vector<int> ed[N];
int main(){
ll n,m,k;cin >> n >> m >> k;
for(int i = 1;i <= m;i++){
int u,v;cin >> u >> v;
// cin >> edge[i].frist >> edge[i].second;
edge[i] = {u,v};
ed[u].push_back(v);
ed[v].push_back(u);
}
queue<int> qu;
qu.push(1);
vis[1] = 1;
while(!qu.empty()){
int u = qu.front();qu.pop();
for(auto v:ed[u]){
if(vis[v]) continue;
vis[v] = 1;
dis[v] = dis[u] + 1;
qu.push(v);
}
}
ll ans = 0;
for(int i = 1;i <= m;i++){
int u = edge[i].first,v = edge[i].second;
if(!vis[u]) continue;
if(dis[u] > dis[v]) swap(u,v);
if(dis[v] == dis[u] + 1 && !use[v]){
use[v] = 1;
}else{
ans += max(2*k - dis[u] - dis[v],(ll)0);
}
}
for(int i = 1;i <= n;i++)
if(vis[i] && dis[i] <= k)
ans++;
for(int i = 2;i <= n;i++){
if(vis[i] && ed[i].size() == 1){
ans += max((ll)0,k - dis[i]);
}
}
cout << ans << endl;
}
题意：一开始为\((1,1,1)\)，每次变成\((a_y,b_z,c_x)\)，问变成\((x_i,y_i,z_i)\)的最小次数，如果不可能输出-1
思路：三个1会从各自位置经过特定的循环变换，由于\(a,b,c\)序列是有限的，因此它一定是有特定周期的，比如在x位置的1，会通过c变换到z位置，然后通过b变换到y位置，然后通过a变换回到x位置
注意不是x，y，z有特定的周期，而是这个转移的数会回到原本位置的1
然后枚举枚举三种状态的最早出现时间，结合周期用exCRT就可以得出答案了
还要开__int128
#include<bits/stdc++.h>
using namespace std;
#define ll __int128
__int128 read()
{
//直接在函数里面实现读字符串操作更简洁
__int128 res=0;//初始结果赋值0
char scan[1005];
scanf("%s",scan);
for(int i=0;i<strlen(scan);i++)
res*=10,res+=scan[i]-'0';//实现进位
return res;//返回__int128类型
}
void print(__int128 num)
{//递归调用，实现从高位向低位输出
if(num>9)
print(num/10);
putchar(num%10+'0');
}
const int N = 1e5 + 10;
const ll INF = 1e18;
ll T[4],t[4],a[N],b[N],c[N];
ll apper[4][4][N];
ll gc;
void exgcd(ll a,ll b,ll &x,ll &y)
{
if(b == 0)
{
x = 1;
y = 0;
gc = a;
return;
}
exgcd(b,a%b,y,x);
y-=a/b*x;
return;
}
ll excrt(int n){
ll lcm = T[1],x = t[1];
for(int i = 2;i <= n;i++)
{
ll a = T[i],aa = t[i];
ll t1,t2;
exgcd(lcm,a,t1,t2);
if((aa-x)%gc != 0){
return INF;
}
t1 = t1*(aa-x)/gc;
x = (t1*lcm+x);
lcm = lcm*a/gc;
x = (x%lcm+lcm)%lcm;
}
return x;
}
int main(){
int n;cin >> n;
for(int i = 1;i <= n;i++) a[i] = read();
for(int i = 1;i <= n;i++) b[i] = read();
for(int i = 1;i <= n;i++) c[i] = read();
ll x = 1,y = 1,z = 1,step = 0,Ta,Tb,Tc;
do{
apper[1][1][x] = step++;
x = c[x];
apper[3][2][x] = step++;
x = b[x];
apper[2][3][x] = step++;
x = a[x];
}while(x != 1);
Ta = step;
step = 0;
do{
apper[2][1][y] = step++;
y = a[y];
apper[1][2][y] = step++;
y = c[y];
apper[3][3][y] = step++;
y = b[y];
}while(y != 1);
Tb = step;
step = 0;
do{
apper[3][1][z] = step++;
z = b[z];
apper[2][2][z] = step++;
z = a[z];
apper[1][3][z] = step++;
z = c[z];
}while(z != 1);
Tc = step;
int q;cin >> q;
while(q--){
x = read();
y = read();
z = read();
ll ans = INF;
if(((t[1] = apper[1][1][x]) || x == 1) && ((t[2] = apper[2][1][y]) || y == 1) && ((t[3] = apper[3][1][z]) || z == 1)){
T[1] = Ta,T[2] = Tb,T[3] = Tc;
ans = min(excrt(3),ans);
}
if((t[1] = apper[1][2][x]) && (t[2] = apper[2][2][y]) && (t[3] = apper[3][2][z])){
T[1] = Tb,T[2] = Tc,T[3] = Ta;
ans = min(excrt(3),ans);
}
if((t[1] = apper[1][3][x]) && (t[2] = apper[2][3][y]) && (t[3] = apper[3][3][z])){
T[1] = Tc,T[2] = Ta,T[3] = Tb;
ans = min(excrt(3),ans);
}
if(ans == INF)
cout << -1 << endl;
else{
print(ans);
cout << endl;
}
}
}
题意：给容量分别为A与B的水杯，问确切喝到X水的最小操作次数
有4种操作：选一杯全喝，选一杯全部倒掉，选一杯装满，将一杯的水尽量倒到另一杯中
思路：不难发现，只有\(Ax+By=X\)有解时才能确切喝到X水
并且当x与y均为正时，最小操作次数为\(2(x+y)\)，符号相反时最小操作次数为\(2(abs(x)+abs(y)) - 1\)，第一个好理解，第二个就是当符号相反时就倒到最大容量的水杯中然后一份一份倒到小杯的水杯中，然后将小杯的水杯倒掉，在最后直接喝水就不需要倒掉小杯的水杯，因此-1
因此我们就要找\(Ax+By=X\)的一个解使得\(abs(x)+abs(y)\)最小，用拓展欧几里得可得到一个可行解，同时\(xy\)有等价关系，当\(x+kB/gc，y-kA/gc\)等价，因此只要枚举让x刚好大于0，刚好小于0，等于0，让y刚好大于0，刚好小于0，等于0的6种可能情况即可得出答案
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll gc;
void exgcd(ll a,ll b,ll &x,ll &y)
{
if(b == 0)
{
gc = a;
x = 1;
y = 0;
return;
}
exgcd(b,a%b,y,x);
y-=a/b*x;
return;
}
//得出ax+by=gcd(a,b)的一个可行解
//如果a,b互素,那么x就为a在(mod b)意义下的逆元,因此也可以求逆元
ll f(ll x,ll y,ll k,ll aa,ll bb){
return abs(x + k*aa) + abs(y - k*bb);
}
int main(){
int t;cin >> t;
while(t--){
ll a,b,c,x,y;cin >> a >> b >> c;
exgcd(a,b,x,y);
if(c % gc != 0)
cout << -1 << endl;
else{
x *= c / gc,y *= c / gc;
ll xx = x,yy = y;
ll bb = a/gc,aa = b/gc;
ll k1 = -x/aa,k2 = -y/bb;
if(f(x,y,k1,aa,bb) < f(xx,yy,0,0,0))
xx = x + k1*aa,yy = y - k1*bb;
if(f(x,y,k1 + 1,aa,bb) < f(xx,yy,0,0,0))
xx = x + (k1 + 1)*aa,yy = y - (k1 + 1)*bb;
if(f(x,y,k1 - 1,aa,bb) < f(xx,yy,0,0,0))
xx = x + (k1 - 1)*aa,yy = y - (k1 - 1)*bb;
if(f(x,y,- k2,aa,bb) < f(xx,yy,0,0,0))
xx = x - k2*aa,yy = y + k2*bb;
if(f(x,y,- k2 - 1,aa,bb) < f(xx,yy,0,0,0))
xx = x - (k2 + 1)*aa,yy = y + (k2 + 1)*bb;
if(f(x,y,- k2 + 1,aa,bb) < f(xx,yy,0,0,0))
xx = x - (k2 - 1)*aa,yy = y + (k2 - 1)*bb;
if(xx*yy < 0)
cout << (abs(xx) + abs(yy)) * 2 - 1 << endl;
else
cout << (abs(xx) + abs(yy)) * 2 << endl;
}
}
}