Codeforces每日一练 150A+776D+721C
传送门
数论水题
题意：给一个数q，写出q的因子p，并用p替换q，p不能等于q或1，谁先不能写谁就赢（注意胜负条件，de了半天发现题意看错了）
很明显，谁拿到质数谁就赢了，那就是质因子分解裸题啦
如果q是两个质数的乘积，那么无论怎么写都是对手第一个得到质数，必输
其他情况下，如果质因子数>=2，任意选两个即可，如果是1，就输出质因子的平方，如果本身是质数或一，输出0
#include
using namespace std;
typedef long long ll;
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);
#define maxn 300005
#define for_(i,n) for(ll (i)=1;(i)<=(n);i++)
vector ans;
int main(){
IOS
ll q;
cin>>q;
ll tmp=q;
for (int i = 2; i 1)ans.push_back(q);
if(ans.size()>2){
cout<<"1"<<endl;
cout<<ans[0]*ans[1];
}else{
if(ans.size()==2){
if(tmp!=ans[0]*ans[1]){cout<<1<<'\n'<<ans[0]*ans[1];}
else cout<<2;
}
else if(ans.size()==1){
if (tmp!=ans[0]){
if(tmp!=ans[0]*ans[0])cout<<1<<'\n'<<ans[0]*ans[0];
else cout<<2;
}
else cout<<1<<"\n"<<0;
}
else cout<<1<<'\n'<<0;
}
return 0;
}
776D The Door Problem
传送门
并查集水题
很明显用洛谷关押罪犯的思路即可
关押罪犯
题意：每个门有其初始状态并由两个开关控制，每个开关可控制多个门，每次使用开关会使其控制的门的状态取反（开->关，关->开），询问能否使所有的门都变成开。
对每个门考虑，如果是开，那么该门的两个开关要么都使用，要么都不使用，如果是关，那么两个开关必须使用其中一个（该情况下，假设两个开关互为“敌人”）。
显然就是并查集的思路了，如果是开，合并两个开关并合并两个开关的“敌人”，如果是关，将每个开关分别和另一个开关的“敌人”集合合并。
#include
using namespace std;
typedef long long ll;
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);
#define maxn 100005
#define for_(i,n) for(ll (i)=1;(i)<=(n);i++)
int f[maxn],enemy[maxn];
int findfa(int x){
if(x==f[x])return x;
else {
f[x]=findfa(f[x]);
return f[x];
}
}
void mergefa(int a,int b){
int fa=findfa(a),fb=findfa(b);
if(fa==fb)return ;
else{
f[fa]=fb;
return ;
}
}
vector s[maxn];
int r[maxn];
int main(){
IOS
int n,m;
cin>>n>>m;
for_(i,n)cin>>r[i];
for_(i,m){
int x;
cin>>x;
while(x--){
int a;
cin>>a;
s[a].push_back(i);
}
}
for_(i,m)f[i]=i;
for_(i,n){
int a=s[i][0],b=s[i][1];
if(r[i]==1){
mergefa(a,b);
if(enemy[a]!=0&&enemy[b]!=0)mergefa(enemy[a],enemy[b]);
else if(!enemy[a])enemy[a]=findfa(enemy[b]);
else if(!enemy[b])enemy[b]=findfa(enemy[a]);
}
if(r[i]==0){
if(!enemy[a])enemy[a]=findfa(b);
else f[findfa(enemy[a])]=findfa(b);
if(!enemy[b])enemy[b]=findfa(a);
else f[findfa(enemy[b])]=findfa(a);
}
}
for_(i,n){
int a=s[i][0],b=s[i][1];
if(r[i]==0)
if(findfa(a)==findfa(b)){
cout<<"NO";
return 0;
}
if(r[i]==1)
if(findfa(enemy[a])==findfa(b)||findfa(enemy[b])==findfa(a)){
cout<<"NO";
return 0;
}
}
cout<<"YES";
return 0;
}
721C Journey
传送门
DAG+dp
题意：DAG里每条路有一个权值代表时间，问在时间T内，从1走到n最多可以游览多少景点（我也想旅游（悲））。
之前没怎么做过dag上的dp，然后写个dfs还T了QAQ。
（百度到一般是拓扑排序+dp，具体原因等我学了再来填坑吧）
可以考虑dp[i][j]代表走到景点i且一共游览了j个景点的最小用时，由于还要输出方案，考虑用一个pre二维数组记录。如果dp[i][j]>dp[x][j-1]+w，那么pre[i][j]=x。
转移完成后，从n到2遍历dp[n][i]，找出符合时间小于T的i的最大值，输出i，然后沿着pre数组一路找，并且把路上的景点存到栈里。最后输出栈里元素即可。
#include
using namespace std;
typedef long long ll;
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);
#define maxn 5005
#define inf 1000000002
#define for_(i,n) for(ll (i)=1;(i)<=(n);i++)
int n,m,t;
struct node{
int v,w;
};
vector g[maxn];
int dp[maxn][maxn];
int pre[maxn][maxn];
int de[maxn];
stack ans;
queue q;
int main(){
IOS
cin>>n>>m>>t;
for_(i,m){
int u,v;
int ti;
cin>>u>>v>>ti;
g[u].push_back({v,ti});de[v]++;
}
while(q.size()!=n){
for_(i,n){
if(de[i]==0){
de[i]--;
q.push(i);
for (auto j:g[i]){
de[j.v]--;
}
}
}
}
for_(i,n)for_(j,n)dp[i][j]=inf;
dp[1][1]=0;
while(!q.empty()){
int now=q.front();
q.pop();
for(auto i:g[now]){
int v=i.v,w=i.w;
for_(j,n-1){
if(dp[now][j]+w=2 ; --k) {
if(dp[n][k]<=t){
cout<<k<<endl;
int i=n,tmp=k;
while(i!=0){
ans.push(i);
i=pre[i][tmp];
tmp--;
}
break;
}
}
while(!ans.empty()){
cout<<ans.top()<<" ";
ans.pop();
}
return 0;
}
这里度数–可以换成开一个vis数组。
（注意空间限制，开ll会mle。
作者：Bazoka13
