A. Dungeon
对于每次到7,它都会增加两点伤害,题目问什么时候同时死,你直接模拟它们死光需要多少轮,以及是不是在这些轮里有人提前死了,判断一下就好了.
#include <bits/stdc++.h>
using namespace std;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int a,b,c;
cin>>a>>b>>c;
int num=(a+b+c)/9;
if((a+b+c)%9==0&&(a>=num&&b>=num&&c>=num)) puts("YES");
else puts("NO");
}
return 0;
} B.Find The Array
已知两种构造方式:一种是构造二进制的最高位的数,另外一种是1,ai/ai,1这样构造
A.对于前者的做法来说呢,就是说因为一个数-一个数的最高位的数<一个数的最高位的数.所以相减的总和*2会小于原本的总和.
B.第二种分奇偶,肯定是有一半>=sum/2,另外一半<=sum/2的.
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,_;
for(cin>>_;_;_--)
{
cin>>n;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
cout<<(1<<(int)log2(x))<<' ';
}puts("");
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+50;
int t[N],x[N];
int main()
{
int T;
scanf("%d",&T);
//T=1;
while(T--)
{
int n;cin>>n;
ll sum=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&x[i]);
sum+=x[i];
}
ll res=0;int flag1=0,flag2=0;
for(int i=1;i<=n;i++)
{
if(i&1) res+=abs(x[i]-1);
}
if(res*2<=sum) flag1=1;
else flag2=1;
if(flag1)
{
for(int i=1;i<=n;i++)
{
if(i&1) cout<<1<<' ';
else cout<<x[i]<<' ';
}
}
if(flag2)
{
for(int i=1;i<=n;i++)
{
if(i&1) cout<<x[i]<<' ';
else cout<<1<<' ';
}
}
puts("");
}
return 0;
} C. Busy Robot
题意很糟糕,读了很久.
题意:给你个机器人,每次在时间下达一个指令让它从当前位置走到
,如果下达指令的时候正在执行的指令没有执行完(也就是没走到该走的位置)，下达的指令就会被忽略.定义一个指令是合法的，当且仅当在这个指令和下个指令的时间段内(闭区间)，机器人走到了这个指令要求的位置.问你有多少个指令合法?
思路:模拟就好.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ti[N],x[N];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int lsq = 0;
int n;
scanf("%d",&n);
ll d = 0,ans = 0;
ll pos = 0,lst = 0,lstposx;
bool ok = 1;
for(int i = 1;i <= n;i++) scanf("%lld%lld",&ti[i],&x[i]);
for(int i = 1;i <= n;i++)
{
ll lstpos = 0;
if(ok)
{
ok = 0;
if(pos <x[i])d = 1;
else if(pos >x[i])d = -1;
else
{
ok = 1;
ans++;
}
lst = ti[i],lstposx =x[i];
}
else
{
lstpos = pos;
pos += d*(ti[i] - lst);
if(d == 1)
{
if(pos >= lstposx)
{
pos = lstposx;
ok = 1;
}
}
else if(d == -1)
{
if(pos <= lstposx){
pos = lstposx;
ok = 1;
}
}
if(min(lstpos,pos)<=lsq&&lsq <= max(pos,lstpos))
{
ans++;
}
lst = ti[i];
if(ok)
{
lstposx=x[i];
if(pos <x[i])d = 1;
else if(pos >x[i])d = -1;
ok = 0;
}
}
if(i==n)
{
if((pos<=x[i]&&x[i]<=lstposx&&d==1)||(pos>=x[i]&&x[i]>=lstposx&&d==-1)) ans++;
}
lsq=x[i];
}
printf("%lld\n",ans);
}
return 0;
}D:Pairs
题意简单,不说明了.想y了...
解法就是:田忌赛马,直接贪心就好了,两者都取最优解.
然后就是答案.
代码如下:
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+50;
int a[N<<1],b[N<<1];
bool vis[N<<1];
int main()
{
int _;
for(cin>>_;_;_--)
{
int n,id=0;cin>>n;
for(int i=1;i<=(n<<1);i++) vis[i]=false;
for(int i=1;i<=n;i++) cin>>a[i],vis[a[i]]=true;
for(int i=1;i<=2*n;i++)
{
if(!vis[i]) b[++id]=i;
}sort(a+1,a+1+n);
int max_x=0,min_x=0;
//贪心怼就完事.类似田忌赛马?
int j,i;i=n;
for(j=n;j>=1;j--)//求min_x
{
if(a[i]<b[j]&&i) min_x++,i--;
else
{
while(i&&a[i]>b[j]) i--;
if(i) min_x++,i--;
}
}min_x=n-min_x;
j=n;
for(i=n;i>=1;i--)//求max_x
{
if(a[i]>b[j]&&j) max_x++,j--;
else
{
while(j&&a[i]<b[j]) j--;
if(j) max_x++,j--;
}
}
cout<<abs(max_x-min_x)+1<<endl;
}
return 0;
}E.Plan of Lectures
首先可知,给定的一定是颗树,然后我们可以把要连在一起的放在同一个并查集里面,我们先预先遍历一遍,假如它们所在同一颗子树,那么可以提前处理出来,因为一定是符合拓扑序的,然后就是遍历这颗树,假如是单个的,直接加入答案,在并查集里面的呢,除非全部都遍历了,类似bfs吧?然后这样就好了.
#include <bits/stdc++.h>
using namespace std;
const int N=3e5+500;
vector<int>v[N];
int fa[N],sz[N],nex[N],n,m;
bool vis[N];
int dsu(int u)
{
if(u==fa[u]) return u;
else return fa[u]=dsu(fa[u]);
}
//提前处理下树上相邻的情况,以及成环情况.
bool ck()
{
for(int i=1;i<=n;i++)
{
if(!vis[dsu(i)])
{
int u=dsu(i);
while(nex[u])
{
if(vis[u]) return false;//成环了.
vis[u]=true;int num=v[u].size();
for(int i=0;i<num;i++)
{
int son=v[u][i];
if(dsu(son)!=dsu(u)) continue;
if(vis[son]) return false;
else sz[dsu(u)]--;//处理下在树上某个节点下方的情况.
}
u=nex[u];
}
}
}return true;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
fa[i]=i,sz[i]=1;
int x;scanf("%d",&x);
v[x].push_back(i);
}//建树
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
sz[dsu(x)]+=sz[dsu(y)];
fa[dsu(y)]=dsu(x);
nex[x]=y;
}
deque<int>q;
vector<int>ans;
if(!ck())
{
puts("0");
}
else
{
for(int i=0;i<=n;i++) vis[i]=false;
//遍历树寻求答案.
q.push_back(0);
while(q.size())
{
int u=q.front();q.pop_front();
if(u) ans.push_back(u);
if(nex[u]) q.push_front(nex[u]);
int num=v[u].size();
for(int i=0;i<num;i++)
{
int son=v[u][i];
if(!vis[dsu(son)]) sz[dsu(son)]--;
if(!vis[dsu(son)]&&!sz[dsu(son)]) q.push_back(dsu(son)),vis[dsu(son)]=true;
}
}
int num=ans.size();
if(num==n)
{
for(int i=0;i<n;i++) printf("%d ",ans[i]);puts("");
}
else puts("0");
}
return 0;
}
京公网安备 11010502036488号