Codeforces Round #843 (Div. 2)（B，C，D，E）
23年的第一场比赛（现场的），结果还是只是做出了两个题
B
想起这道题就好笑，我又又又看错题了，这个题里面讲的一直是或，我在比赛全程都以为是异或，还在怀疑案列不对，真的太伤心了
这个题的大意是n个数，但是不是直接给出，而是告诉你这个数的第几位是1（二进制的形式），问我们可以找到两个子序列（所有的数任意删除（可以是0个）一些数）里的所有的数进行或运算，最后的值是一样的
我们可以贪心的看，我们可以让一个子序列是全部的数（一个都不删除）,我们只要找的另外一个ai,就算删除了ai,也不影响结果，那么就一定有一个子序列（只删除ai的序列和全部的序列的或运算结果一样
#include <iostream>
#include <vector>
#include <map>
using namespace std;
int n,k,t;
void solve()
{
cin>>n;
vector<vector<int>>a(n+1);
map<int,int>cnt;
for (int i=1;i<=n;i++)
{
cin>>k;
for (int j=1;j<=k;j++)
{
int x;
cin>>x;
a[i].push_back(x);
cnt[x]++;
}
}
bool yes=true;//一个序列包括所有的的数，一个包括是少了一个的情况，下面是列举少了哪一个数，如果没了这个数，不可以和包括所有的数的序列一样，就不可以存在满足条件的序列了
for (int i=1;i<=n;i++)
{
yes=true;
for (auto x:a[i])//删除第i个数的情况
{
if (cnt[x]==1)
{
yes=false;
break;
}
}
if (yes)
{
cout<<"YES\n";
return ;
}
}
cout<<"NO\n";
return ;
}
int main ()
{
cin>>t;
while (t--)
{
solve();
}
system ("pause");
return 0;
}
C
这个题大意是给我们一个n,一个m,要我们找到一个r（n&n+1&n+2...n&r=m)
我们可以知道&一定会小于等于那个最小的那个，所以m一定是小于等于n的
对于n和m的最高位都是一样（如果有最高位的话），（我们可以知道m小于等于n,那么n的最高位要么要等于n的，要么下于，但是小于的话就要把n的最高变成0，那么最后需要变成000001（那么最高位后面的都要变成0了，那么最后的值一定是0，而m有最高位，那一定不是0，所以是不可的）
而且，我们只可以把1变成0，不可以把0变成1
还有，如果把较高的一个位置的1变成0，那么后面的都会是0（和上面讲过的最高位的1的位置要相同的原理是相同的）
而且，这这个较高的1要变成0的这一个的前一位必须是0（因为我们的答案要把前面那一位变成1，如果前面那一位是1，那么他的前一位就变成0（改变了值，会把原来的1变成0，而m的这一位是1（这个要1变成0的位置是第一个改变值的位置，它前面的都是一样的），那么就不符合条件了，但是如果前一位是0，就算出现了1，也不会有影响）
#include <iostream>
#include <vector>
using namespace std;
#define int long long
int n,m,t;
void solve()
{
cin>>n>>m;
if (m>n)
{
cout<<-1<<'\n';
return ;
}
if (m==n)
{
cout<<n<<'\n';
return ;
}
int f1=-1,f2=-1;//记录最高位
int ans=0;
int i;
for ( i=63;i>=0;i--)
{
int x=(n>>i)&1;
int y=(m>>i)&1;
if (f1==-1&&x)
{
f1=i;
}
if (f2==-1&&y)
{
f2=i;
}
if (f1!=-1&&f2!=-1)
{
if (f1!=f2)//最高位的1一定要相同
{
cout<<-1<<'\n';
return ;
}
break;
}
}
if (f2==-1)//没有最高位
{
f1++;
ans=(1ll<<f1);//我们最需要把最高位变成0，后面的也就会变成0
cout<<ans<<'\n';
return ;
}
ans+=(1ll<<f1);//记录这些没有改变的值
int flag=-1;
i--;
for (;i>=0;i--)
{
int x=(n>>i)&1;
int y=(m>>i)&1;
if (x!=y)
{
if (x==0&&y==1)
{
cout<<-1<<'\n';
return ;
}
if ((n>>(i+1))&1==1) //1变成0的前一位还是1，不可
{
cout<<-1<<'\n';
return ;
}
ans+=(1ll<<(i+1ll));//那么我们把前一位的0变成1
flag=i;
break;
}
else
{
if (x) ans+=1ll<<i;
}
}
for (i--;i>=0;i--)//改变的那个位置后面的m的都是0
{
int x=(n>>i)&1;
int y=(m>>i)&1;
if (y)
{
cout<<-1<<'\n';
return ;
}
}
cout<<ans<<'\n';
return ;
}
signed main ()
{
cin>>t;
while (t--)
{
solve();
}
system ("pause");
return 0;
}
D
这个是好像有很多个点，只有gcd(x,y)>1的两个点才可以连通，我们需要知道s到t的最短路(经过最少的点），还要输出路径
因为用到gcd，我们可以想到分解质因数，对于有相同的质因数的两个数，我们一定是可以连通的，要怎么实现一个连接？
这里我们把x和它的所有质因数都会连接，y也是，对于x,y如果有相同的质因数，那么x和y就连接了
然后就是求最短路了，每一条路的值都是1
要记录路径，就保存一个prei，记录i的前一步是哪一个点
但是为了防止质因数和x混，我们把质因数+n,后面通过判断和n的大小来判断是质因数还是点（题目保证st<=n)
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#include <map>
using namespace std;
const int maxn=1e6+10;
const int inf=0x3f3f3f3f;
int prime[maxn];
int st[maxn],tot;
struct edge
{
int next,to;
}e[maxn<<2];
int cnt,head[maxn];
int dis[maxn];
bool vis[maxn];
int pre[maxn];
int n;
int a[maxn];
struct node
{
int pos,dis;
friend bool operator <(const node x,const node y)
{
return x.dis>y.dis;
}
};
void add(int u,int v)
{
e[++cnt].next=head[u];
e[cnt].to=v;
head[u]=cnt;
return ;
}
void init(int x)
{
for (int i=2;i<=x;i++)
{
if (!st[i])
{
prime[++tot]=i;
st[i]=i;
}
for (int j=1;j<=tot&&prime[j]*i<=x;j++)
{
st[prime[j]*i]=prime[j];
if (i%prime[j]==0) break;
}
}
return ;
}
int dijkstra(int s,int t)
{
memset(dis,inf,sizeof(dis));
priority_queue<node>q;
q.push({s,0});
dis[s]=0;
while (!q.empty())
{
int u=q.top().pos;
// cout<<u<<" ";
q.pop();
if (vis[u]) continue;
vis[u]=true;
for (int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
int w=1;
if (dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
pre[v]=u;
q.push({v,dis[v]});
}
}
}
//cout<<'\n';
//cout<<dis[t]<<" ";
if (dis[t]>=inf) return -1;
return dis[t];
}
void solve()
{
cin>>n;
int mx=0;
for (int i=1;i<=n;i++)
{
cin>>a[i];
mx=max(mx,a[i]);
}
int s,t;
cin>>s>>t;
if (s==t)
{
cout<<1<<'\n'<<s<<'\n';
return ;
}
if (a[s]==a[t])
{
if (a[s]==1)
{
cout<<-1<<'\n';
return ;
}
cout<<2<<'\n'<<s<<" "<<t<<'\n';
return ;
}
init(mx);
map<pair<int,int>,bool>mp;
for (int i=1;i<=n;i++)
{
int now=a[i];
for (int j=now;j>=2;j/=st[j])
{
// cout<<st[j]+n<<" "<<i<<'\n';
if (mp[{i,st[j]}]) continue;
add(st[j]+n,i);
add(i,st[j]+n);
mp[{i,st[j]}]=true;
}
}
int ans=dijkstra(s,t);
if (ans==-1)
{
// cout<<"ans ";
cout<<-1<<'\n';
return ;
}
vector<int>res;
int cur=t;
while (cur!=s)
{
if (cur<=n)
{
res.push_back(cur);
}
cur=pre[cur];
}
res.push_back(s);
cout<<res.size()<<'\n';
for (int i=res.size()-1;i>=0;i--)
{
cout<<res[i]<<" ";
}
cout<<'\n';
return ;
}
signed main ()
{
int t=1;
while (t--)
{
solve();
}
system ("pause");
return 0;
}
E
这个题大意是给我们一个数组，我们可以选择一段,让其中的奇数个位置+1，偶数位置-1要把数组里面的数都变成0
对于正数，我们需要mx次（前缀和最大的那个，大于0）
对于负数，我们需要mi次（前缀和的最小的那个，小于于0）
（对于中间的负数(加起来前缀和是正数的，刚好可以和正数一起变成0）
ans=mx-mi
#include <iostream>
using namespace std;
const int maxn=1e6+10;
#define int long long
int t,n;
int a[maxn];
void solve()
{
cin>>n;
int mx=0,mi=0;
for (int i=1;i<=n;i++)
{
cin>>a[i];
a[i]=a[i-1]+a[i];
mx=max(mx,a[i]);
mi=min(mi,a[i]);
}
int ans=mx-mi;
cout<<ans<<'\n';
return ;
}
signed main ()
{
cin>>t;
while (t--)
{
solve();
}
system ("pause");
return 0;
}