题意：

一种特殊的排列，叫做 k 共素数排列。如果存在恰好 k 个整数 i ，使得 1≤i≤n 和 gcd(pi,i)=1 ，其中 gcd(x,y) 表示 x 和 y 的最大公约数，那么 n 的 p1,p2,⋯,pn 排列称为 n 的 k 同素排列。

给定 n 和 k ，请帮助小栗构造出 k 与 n 的同素排列，或者直接报告没有这样的排列

假设原序列为1,2,3,4,...n
相邻的两个数一定是互质的,我们对于1~k分别进行右移一次,其它数不变
然后1和任何数的gcd都为1,所以k一定不为0

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
int n,k;
void solve() {cin>>n>>k;if(k==0){cout<<-1<<endl;return;}for(int i=2;i<=k;i++) cout<<i<<' ';cout<<1<<' ';for(int i=k+1;i<=n;i++) cout<<i<<' ';cout<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;
//    cin>>t;while(t--) {solve();}return 0;
}

题意：

冰壶是一项运动员在冰面上将石块滑向目标区域的运动。石块距离目标区域中心最近的队伍获胜。

红蓝两队在数轴上比赛。比赛结束后，数轴上还剩下 (n+m) 块石头，其中 n 块属于红队，另外 m 块属于蓝队。红队的第 i颗棋子位于 ai 处，蓝队的第 i 颗棋子位于 bi 处。

假设 c 是目标区域的中心位置。根据上面的描述我们知道，如果存在某个 i 使得 1≤i≤n ，并且对于所有的 1≤j≤m 我们都有 |c−ai|<|c−bj| ，那么红方就赢得了对局。更重要的是，如果满足条件的 i 的数目正好是 p ，那么红方将赢得 p 分。

给定红队和蓝队棋子的位置后，你的任务是确定目标区域中心的位置 c ，从而使红方赢得比赛并尽可能多地得分。注意 c 可以是任何实数，不一定是整数

可以发现我们可以得到相邻两个蓝色中的所有红色,只要选取c为它们的中点即可,而得到了它们,其它的就不可能得到了
同理,我们可以分别得到相邻蓝色之间的红色,以及最左边的红色,以及最右边的红色

注意，迭代器写二分很容易出界

技巧是返回迭代器

//找大于x的最小
auto t=upper_bound(res.begin(),res.end(),x);
if(t!=res.end()){int pos=t-res.begin();int value=res[pos];
}
//找小于x的最大
auto t=lower_bound(res.begin(),res.end(),x);
if(t!=res.begin()){int pos=t-res.begin()-1;int value=res[pos];
}

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=1e5+10;
int sum[N];
int n,m;
void solve() {cin>>n>>m;map<int,int>mp1,mp2;for(int i=0;i<n;i++){int x;cin>>x;mp1[x]++;}for(int i=0;i<m;i++){int x;cin>>x;mp2[x]++;}vector<int>res1,res2;for(auto [u,v]:mp1) res1.push_back(u);for(int i=0;i<(int)res1.size();i++) sum[i+1]=sum[i]+mp1[res1[i]];for(auto [u,v]:mp2) res2.push_back(u);int ans=0;if(res2.size()>1){for(int i=1;i<(int)res2.size();i++){int a=res2[i-1],b=res2[i];auto t1=upper_bound(res1.begin(),res1.end(),a);auto t2=lower_bound(res1.begin(),res1.end(),b);if(t1!=res1.end()&&t2!=res1.begin()){int pos1=t1-res1.begin();int pos2=t2-res1.begin()-1;ans=max(ans,sum[pos2+1]-sum[pos1]);}}}auto t1=lower_bound(res1.begin(),res1.end(),res2[0]);if(t1!=res1.begin()){int p1=t1-res1.begin()-1;ans=max(ans,sum[p1+1]);}auto t2=upper_bound(res1.begin(),res1.end(),res2[(int)res2.size()-1]);if(t2!=res1.end()){int p2=t2-res1.begin();ans=max(ans,sum[(int)res1.size()]-sum[p2]);}if(!ans) cout<<"Impossible"<<endl;else cout<<ans<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--) {solve();}return 0;
}

当然这样写有点麻烦，还有一种方法是把蓝红全排在一起，然后可以得到的就是连续的红色

#include<bits/stdc++.h>
#define endl '\n'
//#define int long long
using namespace std;
int n,m;
void solve() {cin>>n>>m;vector<int>pos;map<int,int>mp;//值为0表示红队,值为1表示蓝队for(int i=1;i<=n;i++){int x;cin>>x;pos.push_back(x);mp[x]=0;}for(int i=1;i<=m;i++){int x;cin>>x;pos.push_back(x);mp[x]=1;}sort(pos.begin(),pos.end());int cnt=0;int maxcnt=0;for(int i=0;i<(int)pos.size();i++){if(mp[pos[i]]==1){if(cnt>maxcnt) maxcnt=cnt;cnt=0;}else cnt++;    }if(cnt>maxcnt) maxcnt=cnt;if(maxcnt==0) cout<<"Impossible"<<endl;else cout<<maxcnt<<endl;
}
int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--) {solve();}return 0;
}

题意：

一个机器人站在一个无限的二维平面上。机器人的程序是长度为 n 的字符串 s1s2⋯sn ，其中 si∈{‘U’,‘D’,‘L’,‘R’} 将从 (0,0) 开始移动，并遵循字符串中的字符所代表的指令。

更具体地说，假设 (x,y) 是机器人的当前坐标。从 (0,0) 开始，机器人重复以下步骤 n 次。在第 i 次过程中：

• 如果 si=‘U’ ，机器人从 (x,y)(x,y) 移动到 (x,y+1) ；
• 如果 si=‘D’ ，机器人从 (x,y)(x,y) 移动到 (x,y−1) ；
• 如果 si=‘L’ ，机器人从 (x,y)(x,y) 移至 (x−1,y) ；
• 如果 si=‘R’ ，机器人从 (x,y)(x,y) 移动到 (x+1,y)。

然而，坐标 (mx,my) 下方埋有地雷。如果机器人在移动过程中踩到 (mx,my) ，就会被炸成碎片。可怜的机器人

你的任务是将字符串中的字符按任意顺序重新排列，这样机器人就不会踩到 (mx,my)

由于只有一个地雷
所以分别按照UDRL全排列的方式走,如果有一种方式没碰到地雷,那么就构造成功,无论怎么走都会碰到地雷,那么Impossible

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
int mx,my;
string s;
void solve() {cin>>mx>>my;cin>>s;map<char,int>mp;for(int i=0;i<(int)s.size();i++) mp[s[i]]++;string tmp="UDLR";sort(tmp.begin(),tmp.end());if(mx==0&&my==0){cout<<"Impossible"<<endl;return;}do{bool ok=true;int x=0,y=0;for(int i=0;i<4;i++){for(int j=0;j<mp[tmp[i]];j++){if(tmp[i]=='U') y++;else if(tmp[i]=='D') y--;else if(tmp[i]=='L') x--;else if(tmp[i]=='R') x++;if(x==mx&&y==my){ok=false;break;}}}if(ok){for(int i=0;i<4;i++){for(int j=0;j<mp[tmp[i]];j++){cout<<tmp[i];}}cout<<endl;return;}}while(next_permutation(tmp.begin(),tmp.end()));cout<<"Impossible"<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--) {solve();}return 0;
}

题意：

Kotori is practicing making fireworks for the upcoming hanabi taikai. It takes her n minutes to make a single firework, and as she is not really proficient in making fireworks, each firework only has a probability of p * $10^{-4}$ to be perfect. After she finishes making a firework, she can just start making the next firework, or take m minutes to light all the remaining fireworks finished before. If there is at least one perfect firework among the lit ones, she will be happy and go to rest. Otherwise, she will continue practicing. Can you tell her the minimum expected practicing time before she goes to rest if she takes the optimal strategy?

设当前状态到最终状态的期望步数为E，假设最优策略是制作k个烟花后再进行燃放，那么当制作k个后没有一个完美的时，燃放失败，那么就得重新制作，仍然制作k个，因为此时我们已经回到了最初状态，那么仍然遵循最优策略，如果不制作k个，那么就不是最优策略了
当前为初始状态，设当前状态到最终状态的期望步数为E，然后我制作了k个烟花并进行燃放来到了下一状态，这一状态和初始状态一样，因而从这一状态到最终状态的期望步数仍为E，其概率为失败k次的概率，两者相乘为（1-q）^k*E，然后再加上这个过程的步数，即n*k+m，这个过程是在最优策略下必然走的，概率为1，乘个1相当于没变
E=n*k+m+(1-q)^k*E
E=(n*k+m)/(1-(1-q)^k)
在得到E的式子之后，我们就需要确定当k为多少时期望步数最少
发现两端一比为正无穷，猜测图像是个开口向上的抛物线，所以利用三分，求极小值所在的横坐标，由于k是整数，所以比较它两端的整数，取函数值更小的那个

#include<bits/stdc++.h>
#include<cstdio>
#define endl '\n'
#define eps 1e-6
//#define int long long
using namespace std;
int n,m,p;
double q;
double f(double x){return (n*x+m)/(1-pow(1-q,x));
}
void solve() {cin>>n>>m>>p;q=p*0.0001;double l=1,r=1e9;while(r-l>eps){double L=(2*l+r)/3,R=(l+2*r)/3;if(f(L)>f(R)) l=L;else r=R;}int x=(int)l;int y=x+1;printf("%.8f\n",min(f(x),f(y)));
}
int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--) {solve();}return 0;
}

题意：

n*m的矩阵，一共有n * m个点，要求给所有点着色，一共有3种颜色，问使得至少存在一个子矩阵相邻的点两两颜色相同的方案数（模1e9+7）

首先可以选取的颜色很少,也就是说很快就会出现重复
选择其中的两行进行研究,由于一共只有3种颜色(1,2,3)那么对于某一列的颜色选取可能为(1,1),(2,2),(3,3),(1,2),(2,1),(1,3),(3,1),(2,3),(3,2)
共有九种,那么当列超过9,根据抽屉原理(鸽巢原理),一定会出现重复,也就是说必然合法
行与列是等价的,所以当max(n,n)>9时,不管怎么着色,一定是合法的,则方案数为3^(n*m)
剩下的就暴力打表,不要怕复杂度为3^81,我们可以在中途剪枝,并且zhi'shi打表对时间要求不高

两种暴力方法：
1.从反面来看，我们求出不合法的方案数，再用总的方案数减去它

具体就是当出现一个子矩阵四个点相邻的点两两颜色相同时，我们就剪枝， 否则就继续搜下去，然后当全搜完了还没有出现一个子矩阵相邻的点两两颜色相同，那么就计数+1

注意，这里写成if() dfs

如果写if() return；由于在循环里，会直接在循环里结束，其它情况还没有试

int res[N][N];
int c[N][N];
int n,m;
int nn,mm;
int cnt;
int pre[N];
bool check(int x2,int y2){for(int x1=1;x1<x2;x1++){for(int y1=1;y1<y2;y1++){if(c[x1][y1]==c[x2][y1]&&c[x1][y2]==c[x2][y2]) return false;if(c[x1][y1]==c[x1][y2]&&c[x2][y2]==c[x2][y1]) return false;}}return true;
}
void dfs(int x,int y){if(y==mm+1){y=1;x++;}if(x==nn+1){cnt=(cnt+1)%mod;return;}for(int color=1;color<=3;color++){c[x][y]=color;if(check(x,y)) dfs(x,y+1);}
}
void solve() {cin>>n>>m;pre[0]=1;for(int i=1;i<=n*m;i++){pre[i]=pre[i-1]*3%mod;}nn=n,mm=m;dfs(1,1);cout<<cnt<<endl;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){nn=i,mm=j;cnt=0;dfs(1,1);res[i][j]=cnt;}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cout<<pre[i*j]-res[i][j]<<' ';}cout<<endl;}
}

2.正面

当存在一个子矩阵相邻的点两两颜色相同，则剩下的点三种颜色随便选

int res[N][N];
int c[N][N];
int n,m;
int nn,mm;
int cnt;
int qmi(int x,int y)
{int res=1;while(y){if(y&1) res=res*x%mod;x=x*x%mod;y>>=1;}return res%mod;
}
bool check(int x2,int y2){for(int x1=1;x1<x2;x1++){for(int y1=1;y1<y2;y1++){if(c[x1][y1]==c[x2][y1]&&c[x1][y2]==c[x2][y2]) return false;if(c[x1][y1]==c[x1][y2]&&c[x2][y2]==c[x2][y1]) return false;}}return true;
}
void dfs(int x,int y){if(y==mm+1){y=1;x++;}if(x==nn+1){return;}for(int color=1;color<=3;color++){c[x][y]=color;if(!check(x,y)){int tot=nn*mm-(x-1)*mm-y;cnt=(cnt+qmi(3,tot))%mod;}else dfs(x,y+1);}
}
void solve() {cin>>n>>m;nn=n,mm=m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){nn=i,mm=j;cnt=0;dfs(1,1);res[i][j]=cnt;}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cout<<res[i][j]<<' ';}cout<<endl;}
}

要优先判断n为1或者m为1，n为1或m为1答案一定为0，打的表不够大

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int mod=1e9+7;
int n,m;
int res[9][9]={0, 0, 0, 0, 0, 0, 0, 0, 0,0, 15, 339, 4761, 52929, 517761, 4767849, 43046721, 387420489,0, 339, 16485, 518265, 14321907, 387406809, 460338013, 429534507, 597431612,0, 4761, 518265, 43022385, 486780060, 429534507, 792294829, 175880701, 246336683,0, 52929, 14321907, 486780060, 288599194, 130653412, 748778899, 953271190, 644897553,0, 517761, 387406809, 429534507, 130653412, 246336683, 579440654, 412233812, 518446848,0, 4767849, 460338013, 792294829, 748778899, 579440654, 236701429, 666021604, 589237756,0, 43046721, 429534507, 175880701, 953271190, 412233812, 666021604, 767713261, 966670169,0, 387420489, 597431612, 246336683, 644897553, 518446848, 589237756, 966670169, 968803245
};
int qmi(int a,int b){int res=1;while(b){if(b&1) res=res*a%mod;a=a*a%mod;b>>=1;}return res;
}
void solve() {cin>>n>>m; if(n==1||m==1) cout<<0<<endl;else if(n>9||m>9) cout<<qmi(3,n*m)<<endl;else cout<<res[n-1][m-1]<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--) {solve();}return 0;
}

题意：

有一棵有根的树，其顶点为 n ，根顶点为 1 。每个顶点都有一个怪物。位于 i-th顶点的怪物的命中点数为 hpi 。

小栗想杀死所有的怪物。如果 i -th顶点的直系父节点上的怪物已经被杀死，那么 i -th顶点上的怪物就可以被杀死。杀死 i -th怪物所需的力量是 hpi 和所有其他生活在顶点 j 中的怪物的命中率之和，而顶点 j 的直接父节点是 i

此外，小鸟还可以使用一些魔法咒语。只要使用一个魔法咒语，她就可以使用 0 的力量杀死任何怪物，不受任何限制。也就是说，即使直系亲属中的怪物还活着，她也可以选择一个怪物。

对于每个 m=0,1,2,⋯,n，小栗分别想知道，如果她可以使用 m 个魔法，杀死所有怪物所需的最小总能量

树形背包dp
选与不选->有限制的选择->背包

首先，我去了解了一下树形背包dp，一般是三维dp[u] [i] [j]，表示以u为根的子树，枚举到它的第i个子树，总体积等于j所获得的最大价值

然后可以优化掉第二维，只要将j倒序即可

然后树形背包一般是O($n^3$)，然后可以优化成O($n^2$)

我们这里就直接记忆O($n^2$)的写法，具体写法是这样的：

记忆点：

1. 用已经求好的答案更新未来的问题
2. j的范围是前面已经统计过的子树，k的范围是当前的子树，当前算法就是在枚举当前子树v和之前已经枚举过的所有子树的点对，设(a,b)是任意一个点对，则它只会在遍历lca(a,b)时被枚举一次，所以是O($n^2$)，由此siz[u]是最后加siz[v]
3. 一般j是放进背包里的个数，对应到这题，用魔法的是0代价，相当于删除，其它的相当于存活，也就是说被选进背包里的，所以这题j一般表示剩余的个数

void dfs(int u,int fa){siz[u]=1;dp[u][0][0]=0,dp[u][1][1]=h[u];//初始化dpfor(auto v:e[u]){if(v==fa) continue;dfs(v,u);for(int j=siz[u];j>=0;j--){//倒序,滚动数组,优化掉一维for(int k=siz[v];k>=0;k--){//决策,正序倒序好像都可以dp[u][j+k][1]= min(dp[u][j+k][1], dp[u][j][1] + min(dp[v][k][0], dp[v][k][1]+h[v]));dp[u][j+k][0]= min(dp[u][j+k][0], dp[u][j][0] + min(dp[v][k][0], dp[v][k][1]));}}siz[u]+=siz[v];}
}

若u是用魔法打败的，那么顺序必然为先用魔法打败u，再去打u的孩子，这样u的孩子可以选择不用魔法。
若u不是用魔法打败的，最终打败u的代价还需要加上其孩子中不使用魔法的hp，因为这些不使用魔法打败的孩子，必然是在u被打败之后才被打败，即在u未被打败的时候这些孩子还存活

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=2e3+10;
int p[N];
int h[N];
int siz[N];
int n;
int dp[N][N][2];//dp[u][j][0/1]表示以u为根的子树,j个节点没有使用魔法,u不使用魔法(1),u使用魔法(0)的最小代价
vector<vector<int>>e(N);
void dfs(int u,int fa){siz[u]=1,dp[u][0][0]=0,dp[u][1][1]=h[u];for(auto v:e[u]){if(v==fa) continue;dfs(v,u);for(int j=siz[u];j>=0;j--){for(int k=siz[v];k>=0;k--){dp[u][j+k][1]= min(dp[u][j+k][1], dp[u][j][1] + min(dp[v][k][0], dp[v][k][1]+h[v]));dp[u][j+k][0]= min(dp[u][j+k][0], dp[u][j][0] + min(dp[v][k][0], dp[v][k][1]));}}siz[u]+=siz[v];}
}
void solve() {cin>>n;for(int i=1;i<=n;i++) e[i].clear();for(int i=2;i<=n;i++) {cin>>p[i];e[i].push_back(p[i]);e[p[i]].push_back(i);}for(int i=1;i<=n;i++) cin>>h[i];for(int i=0;i<=n;i++){for(int j=0;j<=n;j++){dp[i][j][0]=dp[i][j][1]=1e18;}}dfs(1,-1);for(int i=n;i>=0;i--) cout<<min(dp[1][i][0],dp[1][i][1])<<' ';cout<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--) {solve();}return 0;
}