牛客小白月赛19
牛客小白月赛19
D.「金」初心如金 题意：给n，首先给一个奇数，如果这个数是素数则ans=1，否则ans=0
接下来n-1次原本也是给一个奇数，但实际给的数=lastans^原本要给的奇数
问前n-1个数的ans是多少(是素数为1，不是素数为0)，输出这个ans
因为每次给的都是奇数，而每一次实际给的数=lastans^原本要给的奇数，
所以我们可以通过实际给的数，倒推出lastans的值。
题目输入的最后一个数不需要输出也暗示了做法。
#include
using namespace std;
#define ll long long
signed main(){
signed n;
scanf("%d",&n);
ll x;
scanf("%lld",&x);
for(int i=2;i<=n;i++){
scanf("%lld",&x);
if(x&1)puts("0");
else puts("1");
}
return 0;
}
E.「火」烈火燎原
题意：
现在有一棵树G（无环），定义它的“小树”是X(G)，小树X(G)的点集是G的边集
在“小树”中，两点之间有边，当且仅当这两个点对应的边在原图上有公共点
给定一棵树G，它的X(X(G))有多少个点？
X(G)的点数是G的边数，
假设G中点x的度为k，即这k条边都连接x，那么X(G)中对应的这K个点相邻，两两匹配共有k(k-1)/2个边
所以X(G)中边的数量就是d(i)(d(i)-1)/2，又因为X(G)的点数是G的边数，
所以X(X(G))的点数就是原图中的d(i)(d(i)-1)/2
#include
using namespace std;
#define int long long
const int maxm=1e5+5;
int d[maxm];
signed main(){
int n;
cin>>n;
for(int i=1;i>a>>b;
d[a]++;
d[b]++;
}
int ans=0;
for(int i=1;i<=n;i++){
ans+=d[i]*(d[i]-1)/2;
}
cout<<ans<<endl;
return 0;
}
H.「土」巨石滚滚
题意：
有一个土球和n个障碍
土球有一个稳定性x，如果x < 0，它会立刻散架
每冲撞一个障碍，土球会丧失ai的稳定性，冲撞之后，又会从障碍身上回馈bi的稳定性
能否合理的安排障碍的顺序，在保证土球不散架的情况下，是否可以将障碍全部撞毁呢？
可以输出yes，不可以输出no
bzoj3709原题
贪心。
把障碍分成两种，第一种是回复>伤害的，按照伤害从低到高去打就是最优的。
第二种是伤害>回复的。通过所有障碍的时候，血量一定是固定的，所以要先过回血多的，再过回血少的。
#include
using namespace std;
#define int long long
struct Node{
int a,b;
};
vectorl,r;
bool cmp1(Node a,Node b){
return a.ab.b;
}
signed main(){
int T;
cin>>T;
while(T--){
l.clear();
r.clear();
int n,x;
cin>>n>>x;;
for(int i=1;i>a>>b;
if(a<=b)l.push_back({a,b});//回血
else r.push_back({a,b});//掉血
}
sort(l.begin(),l.end(),cmp1);
sort(r.begin(),r.end(),cmp2);
int ok=1;
for(auto i:l){
if(!ok)break;
if(x<=i.a){
ok=0;
}else{
x-=i.a;
x+=i.b;
}
}
for(auto i:r){
if(!ok)break;
if(x<=i.a){
ok=0;
}else{
x-=i.a;
x+=i.b;
}
}
if(ok)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}
I
J
作者：我到底在干嘛
