北京信息科技大学第十二届程序设计竞赛暨ACM选拔赛题解
A 爱丽丝的人偶（一）
链接：https://ac.nowcoder.com/acm/contest/8755/A
题目描述
爱丽丝有个人偶，每个人偶的身高依次是
现在她要将这个人偶摆成一排。
但是人偶被设置了魔法。假设对一个非两端的（不在队首也不在队尾）人偶而言，她相邻的两个人偶，一个比高、一个比矮，那么就会爆炸。
爱丽丝想找到一种摆法，使得所有人偶都不会爆炸。你能帮帮她吗？
输入描述:
一个正整数
输出描述:
满足要求的一种摆法。如果有多解，输出任意一种摆法即可。
示例1
输入
3
输出
1 3 2
说明
对于第二个人偶，她两边的两个人偶都比她矮，满足要求。
另外，[3 1 2]、 [2 1 3] 、[2 3 1]这三种摆法也都满足要求。输出这三种摆法也视为正确。
思路
从小到大，除了第一个，两两交换一下顺序。
拼手速！
代码
#include <bits/stdc++.h>
typedef long long ll;
const ll mod = 9999999967;
using namespace std;
namespace fastIO {
inline void input(int& res) {
char c = getchar();res = 0;int f = 1;
while (!isdigit(c)) { f ^= c == '-'; c = getchar(); }
while (isdigit(c)) { res = (res << 3) + (res << 1) + (c ^ 48);c = getchar(); }
res = f ? res : -res;
}
inline ll qpow(ll a, ll b) {
ll ans = 1, base = a;
while (b) {
if (b & 1) ans = (ans * base % mod +mod )%mod;
base = (base * base % mod + mod)%mod;
b >>= 1;
}
return ans;
}
}
using namespace fastIO;
const int N = 1e6 + 5;
int Case,n;
int a[N];
void solve(){
input(n);
for(int i=1;i<=n;i++){
a[i]=i;
}
for(int i=2;i<=n-1;i+=2){
swap(a[i],a[i+1]);
}
for(int i=1;i<=n;i++) printf("%d ",a[i]);
}
int main(){
Case=1;
//input(Case);
while(Case--){
solve();
}
return 0;
}
B 爱丽丝的人偶（二）
链接：https://ac.nowcoder.com/acm/contest/8755/B
题目描述
爱丽丝有个人偶，第 个人偶的型号为。
现在爱丽丝要拿出其中个人偶，满足这个人偶的型号互不相同。
爱丽丝想知道自己有多少多不同的方案数？
注：若两个人偶的型号相同，那么无论拿她们中的哪一个都是等价的。
请将方案数对取模。
输入描述:
第一行输入两个正整数和，用空格隔开。
第二行输入个正整数，代表这个人偶的型号。
输出描述:
一个整数，代表最终方案的数量对取模的值。
示例1
输入
5 2
1 2 3 2 1
输出
3
说明
一共有{1,2}{1,3}{2,3}这三种不同的方案（型号组合）。
请注意，拿第一个和第三个、第三个和第五个最终的型号组合都是{1,3}，被视为同一种方案。
思路
统计出现型号种类的个数，然后组合数就行了，注意k大于个数时输出0
手速题
#include <bits/stdc++.h>
typedef long long ll;
const ll mod = 1e9+7;
using namespace std;
namespace fastIO {
inline void input(ll& res) {
char c = getchar();res = 0;int f = 1;
while (!isdigit(c)) { f ^= c == '-'; c = getchar(); }
while (isdigit(c)) { res = (res << 3) + (res << 1) + (c ^ 48);c = getchar(); }
res = f ? res : -res;
}
inline ll qpow(ll a, ll b) {
ll ans = 1, base = a;
while (b) {
if (b & 1) ans = (ans * base % mod +mod )%mod;
base = (base * base % mod + mod)%mod;
b >>= 1;
}
return ans;
}
}
using namespace fastIO;
const int N = 1e6 + 5;
ll Case,n,k,x;
map<ll,ll> mp;
ll f[N];
void init(){
f[0]=1,f[1]=1;
for(int i=2;i<=N-3;i++){
f[i]=f[i-1]*i%mod;
}
}
ll cal(ll n,ll m){
if(n<m) return 0;
return f[n]*qpow(f[n-m],mod-2)%mod*qpow(f[m],mod-2)%mod;
}
void solve(){
ll num = 0;
input(n),input(k);
for(int i=1;i<=n;i++){
input(x);
if(mp[x]==0){
num++;
}
mp[x]++;
}
printf("%lld",cal(num,k));
}
int main(){
Case=1;
//input(Case);
init();
while(Case--){
solve();
}
return 0;
}
C 打毛玉大赛
链接：https://ac.nowcoder.com/acm/contest/8755/C
题目描述
灵梦和萃香正在神社进行打毛玉的比赛。
初始有2只毛玉，它们的血量为和。
两个人轮流行动。灵梦先手。
每回合灵梦可以使用封魔阵，对某一只毛玉造成1点伤害。而萃香能使用户隐山投，对某一只毛玉造成任意点伤害。
两人约定，击杀最后一只毛玉的一方获胜。
假设双方都足够聪明，谁会获得最终的胜利？
输入描述:
两个正整数和，用空格隔开。
输出描述:
如果灵梦获胜，则输出一个字符’A’。
如果萃香获胜，则输出一个字符’B’。
示例1
输入
1 2
输出
A
说明
灵梦先攻击血量为2的毛玉，这时无论萃香击杀哪一只毛玉，灵梦都可以击杀另一只，所以灵梦必胜。
示例2
输入
1 1
输出
B
说明
无论灵梦击杀第一只还是第二只，萃香都能击杀另外一只毛玉。
思路
分析奇异局势，发现1 1就是，而灵梦只有 1 2 或 2 1时才能达到奇异局势
手速题
代码
#include <bits/stdc++.h>
typedef long long ll;
const ll mod = 9999999967;
using namespace std;
namespace fastIO {
inline void input(int& res) {
char c = getchar();res = 0;int f = 1;
while (!isdigit(c)) { f ^= c == '-'; c = getchar(); }
while (isdigit(c)) { res = (res << 3) + (res << 1) + (c ^ 48);c = getchar(); }
res = f ? res : -res;
}
inline ll qpow(ll a, ll b) {
ll ans = 1, base = a;
while (b) {
if (b & 1) ans = (ans * base % mod +mod )%mod;
base = (base * base % mod + mod)%mod;
b >>= 1;
}
return ans;
}
}
using namespace fastIO;
const int N = 1e6 + 5;
int Case,a,b;
void solve(){
input(a),input(b);
if(a==1&&b==2) puts("A");
else if(a==2&&b==1) puts("A");
else puts("B");
}
int main(){
Case=1;
//input(Case);
while(Case--){
solve();
}
return 0;
}
D 贪玩的二小姐（续）
链接：https://ac.nowcoder.com/acm/contest/8755/D
题目描述
芙兰朵露拿到了一个只含有 ‘(’ 和 ‘)’ 这两种字符的字符串。芙兰想玩一玩这个字符串。
现在将字符串括号匹配定义如下：
空字符串： “” 是匹配的。
若字符串是匹配的，那么 “(s)” 是匹配的。
若字符串和都是匹配的，字符串 “st” 是匹配的。
例如，"(()())" 是匹配的 ， "())(()"则不是匹配的。
芙兰朵露每一次操作可以将括号翻转，即把左括号变成右括号，或者把右括号变成左括号。
她想知道将给定的字符串变成匹配的，需要最少的操作次数是多少？
输入描述:
第一行一个正整数，代表给定字符串的长度。(1\leq{n}\leq 10^6)(1≤n≤10
6
)
第二行是一个长度为的、仅含有 '( '和 ‘)’ 这两种字符的字符串。
输出描述:
如果能在有限次操作将字符串变成匹配的，请输出最少的操作次数。
否则输出-1
示例1
输入
4
()))
输出
1
说明
将第三个括号翻转，字符串变成 “()()” ，为匹配的。
示例2
输入
1
(
输出
-1
说明
翻转后字符串变成")"，显然不可能匹配。
思路
奇数是不行的，然后偶数的话将’)‘没法匹配的变成’(’，记录处理次数，然后将剩下’('进行处理，相加即可。
手速题
代码
#include <bits/stdc++.h>
typedef long long ll;
const ll mod = 1e9+7;
using namespace std;
namespace fastIO {
inline void input(ll& res) {
char c = getchar();res = 0;int f = 1;
while (!isdigit(c)) { f ^= c == '-'; c = getchar(); }
while (isdigit(c)) { res = (res << 3) + (res << 1) + (c ^ 48);c = getchar(); }
res = f ? res : -res;
}
inline ll qpow(ll a, ll b) {
ll ans = 1, base = a;
while (b) {
if (b & 1) ans = (ans * base % mod +mod )%mod;
base = (base * base % mod + mod)%mod;
b >>= 1;
}
return ans;
}
}
using namespace fastIO;
const int N = 1e6 + 5;
ll Case,n;
char s[N];
void solve(){
input(n);
int num = 0;
int ans = 0;
int sum = 0;
scanf("%s",s);
for(int i=0;i<n;i++){
if(s[i]=='(') ans++;
else if(s[i]==')'&&ans>0) ans--,num++;
else if(s[i]==')'&&ans==0) ans++,s[i]='(',sum++;
}
if(n%2)
printf("-1");
else
printf("%d",ans/2+sum);
}
int main(){
Case=1;
//input(Case);
while(Case--){
solve();
}
return 0;
}
E 游戏机本当下手
链接：https://ac.nowcoder.com/acm/contest/8755/E
题目描述
藤原妹红拿到了一个游戏机，游戏机上有’1’和’0’两个按钮。
妹红发现，只要按住某个按钮不放，屏幕上就能一直不断打印那个字符。
比如对于"11111111100000000001111111111"，只需要按住1、再按住0、再按住1就可以打印出来了。这样妹红最少只需要按3次按钮就可以打印这个字符串。
现在妹红拿到了一个01字符串，她想截取其中的一个子串，这个子串最少按 次按钮就可以打印出来。
（01字符串指仅由字符’0’和字符’1’组成的字符串）
注意这里“最少按 次”的含义是：按 次可以打印出这个子串，但按 次就一定打印不出这个子串。
妹红想知道，一共有多少子串符合要求？
注：一个字符串的子串为该字符串删掉前面和后面部分字符（也可以不删）生成的字符串。
两个子串只要在字符串中位置不同则认为是不同的（哪怕字符串相等）。
输入描述:
第一行两个正整数 和 ，分别代表字符串的长度、和妹红按下按钮的次数。
第二行为一个仅由字符“0”和“1”组成的字符串。
输出描述:
妹红至少按 次就能按出来的子串的数量。
示例1
输入
6 2
001100
输出
8
说明
注意到k=2，因此要寻找最少按2次就能打印的子串。
s[0,2]=“001”，妹红最少按2次就能按出来，先按0再按1。
s[0,3]=“0011”，妹红最少按2次就能按出来，先按0再按1。
s[1,2]=“01”，妹红最少按2次就能按出来，先按0再按1。
s[0,3]=“011”，妹红最少按2次就能按出来，先按0再按1。
s[2,4]=“110”，妹红最少按2次就能按出来，先按1再按0。
s[2,5]=“1100”，妹红最少按2次就能按出来，先按1再按0。
s[3,4]=“10”，妹红最少按2次就能按出来，先按1再按0。
s[3,5]=“100”，妹红最少按2次就能按出来，先按1再按0。
共有8个子串符合要求。
示例2
输入
3 1
110
输出
4
说明
注意到k=1，因此要寻找按1次就能打印的子串。
s[0,0]=“1”，妹红按住1就可以打印出来，只按了1次按钮
s[0,1]=“11”，妹红按住1就可以打印出来，只按了1次按钮
s[1,1]=“1”，妹红按住1就可以打印出来，只按了1次按钮
s[2,2]=“0”，妹红按住0就可以打印出来，只按了1次按钮
共有4个子串符合要求。
备注:
对于20%的样例，
对于40%的样例，
对于60%的样例，
对于100%的样例，
思路
将每个连续子串的大小记录下就行了，k=1时特判。
手速题
代码
#include <bits/stdc++.h>
typedef long long ll;
const ll mod = 1e9+7;
using namespace std;
namespace fastIO {
inline void input(ll& res) {
char c = getchar();res = 0;int f = 1;
while (!isdigit(c)) { f ^= c == '-'; c = getchar(); }
while (isdigit(c)) { res = (res << 3) + (res << 1) + (c ^ 48);c = getchar(); }
res = f ? res : -res;
}
inline ll qpow(ll a, ll b) {
ll ans = 1, base = a;
while (b) {
if (b & 1) ans = (ans * base % mod +mod )%mod;
base = (base * base % mod + mod)%mod;
b >>= 1;
}
return ans;
}
}
using namespace fastIO;
const int N = 1e6 + 5;
ll Case,n,maxx,q,cnt=1,k,ans=0;
char a[N];
ll b[N];
void solve(){
input(n),input(k);
scanf("%s",a);
for(int i=0;i<n;i++){
b[cnt]=1;
i++;
while(a[i]==a[i-1]){
b[cnt]++;
i++;
}
i--;
cnt++;
}
//for(int i=1;i<cnt;i++) cout<<b[i]<<" ";
//cout<<endl;
if(k!=1){
for(int i=1;i<cnt;i++){
ll aa = 1;
if(i+k-1<cnt){
aa=(b[i]*b[i+k-1]);
ans+=aa;
}
}
}
else{
for(int i=1;i<cnt;i++){
ll sum = 0;
for(int j=1;j<=b[i];j++)
sum=sum+j;
ans += sum;
}
}
printf("%lld",ans);
}
int main(){
Case=1;
//input(Case);
while(Case--){
solve();
}
return 0;
}
F 宵暗的妖怪
链接：https://ac.nowcoder.com/acm/contest/8755/F
来源：牛客网
题目描述
露米娅作为宵暗的妖怪，非常喜欢吞噬黑暗。
这天，她来到了一条路上，准备吞噬这条路上的黑暗。
这条道路一共被分为部分，每个部分上的黑暗数量为。
露米娅每次可以任取 连续的 未被吞噬过的 三部分，将其中的黑暗全部吞噬，并获得中间部分的饱食度。
露米娅想知道，自己能获得的饱食度最大值是多少？
输入描述:
第一行一个正整数，代表道路被分的份数。
第二行有个正整数，代表每一部分黑暗数量。
数据范围：
输出描述:
一个正整数，代表最终饱食度的最大值。
示例1
输入
7
2 4 1 4 2 1 8
输出
6
说明
选择[2,4,1]和[4,2,1]这两段即可。饱食度为4+2=6。
示例2
输入
7
2 4 1 7 2 1 8
输出
7
说明
选择[1,7,2]这一段即可。饱食度为7。
值得注意的是，若取两段进行吞噬，反而最多只能获得6的饱食度，并不是最大的。
思路
用前缀和保存，然后和前几项做比较就行了
思维+手速题
代码
#include <bits/stdc++.h>
typedef long long ll;
const ll mod = 1e9+7;
using namespace std;
namespace fastIO {
inline void input(ll& res) {
char c = getchar();res = 0;int f = 1;
while (!isdigit(c)) { f ^= c == '-'; c = getchar(); }
while (isdigit(c)) { res = (res << 3) + (res << 1) + (c ^ 48);c = getchar(); }
res = f ? res : -res;
}
inline ll qpow(ll a, ll b) {
ll ans = 1, base = a;
while (b) {
if (b & 1) ans = (ans * base % mod +mod )%mod;
base = (base * base % mod + mod)%mod;
b >>= 1;
}
return ans;
}
}
using namespace fastIO;
const int N = 1e6 + 5;
ll Case,n,maxx;
ll sum[N],a[N];
void solve(){
input(n);
for(int i=1;i<=n;i++){
input(a[i]);
if(i>2){
sum[i] = max(sum[i-3]+a[i-1],sum[i-1]);
}
}
printf("%lld",sum[n]);
}
int main(){
Case=1;
//input(Case);
while(Case--){
solve();
}
return 0;
}
G 魔界伊始
链接：https://ac.nowcoder.com/acm/contest/8755/G
题目描述
神崎作为魔界之神，造人的方法是用沙子捏成人形，然后用魔法赋予其意识。
神崎有一台天平以及个砝码，另外她还有很多个同样重的烧杯和无穷多的沙子。平日她通过这些来称量出准确重量的沙子。
她想知道能否利用这些砝码称出重量为的沙子？
一共有次询问。
注：烧杯的数量可以视为无穷多个。烧杯的重量是未知的，但大小可以视为无穷大，即可以装任意多的沙子。烧杯中也可以放砝码。
输入描述:
第一行一个正整数。
第二行有个正整数，代表砝码的重量。
接下来的一行有一个正整数。
接下来的行，每一行有一个正整数，分别代表一次询问。
数据范围：1≤q,n≤100000,1≤a_i,x≤10^{18}1≤q,n≤100000,1≤a i,x≤10^18
输出描述:
输出行。如果能撑出重量为的沙子，则输出"Yes"。否则输出"No"（不包含引号）。
示例1
输入
2
6 20
2
8
7
输出
Yes
No
说明
想要称出重量为8的沙子，可以先用两个砝码称出重量14的沙子，然后用这些沙子和一个重量6的砝码称出重量8的沙子。
但是无论如何，显然都不能称出重量7的沙子。
思路
往能构成最小的重量去考虑，那么能生产的绝对是他的倍数，而你在模拟构成最小的重量的过程和辗转相除一模一样，所以直接__gcd就行了
思维+拼手速
代码
#include <bits/stdc++.h>
typedef long long ll;
const ll mod = 1e9+7;
using namespace std;
namespace fastIO {
inline void input(ll& res) {
char c = getchar();res = 0;int f = 1;
while (!isdigit(c)) { f ^= c == '-'; c = getchar(); }
while (isdigit(c)) { res = (res << 3) + (res << 1) + (c ^ 48);c = getchar(); }
res = f ? res : -res;
}
inline ll qpow(ll a, ll b) {
ll ans = 1, base = a;
while (b) {
if (b & 1) ans = (ans * base % mod +mod )%mod;
base = (base * base % mod + mod)%mod;
b >>= 1;
}
return ans;
}
}
using namespace fastIO;
const int N = 1e6 + 5;
ll Case,n,maxx,q,x;
ll sum[N],a[N];
void solve(){
input(n);
bool flag = false;
for(int i=1;i<=n;i++){
input(a[i]);
}
sort(a+1,a+n+1);
ll minn = 0x3f3f3f3f3f;
for(int i=1;i<n;i++){
ll t = __gcd(a[i],a[i+1]);
//cout<<t<<"-";
minn = min(minn,t);
if(minn == 1) break;
}
//cout<<endl<<"--"<<minn<<endl;
if(minn==1) flag = true;
input(q);
if(flag){
for(int i=1;i<=q;i++){
input(x);
puts("Yes");
}
}
else{
for(int i=1;i<=q;i++){
input(x);
if(x%minn) puts("No");
else puts("Yes");
}
}
}
int main(){
Case=1;
//input(Case);
while(Case--){
solve();
}
return 0;
}
H 芭芭拉冲鸭~
链接：https://ac.nowcoder.com/acm/contest/8755/H
题目描述
芭芭拉拿到了一棵无根树，树上每个节点被染成了红色或绿色或蓝色。（R=红色，G=绿色，B=蓝色）。
任意两点之间的距离均为1。
若一条边连接的两个节点的颜色不同，芭芭拉则可以在这条边上冲刺。
但是，芭芭拉在冲刺的时候不能掉头。例如芭芭拉已经从冲到了，就不能再回到。
现在芭芭拉想知道，自己在这棵树上最远能冲刺的距离是多少？
输入描述:
第一行一个正整数，代表树的节点个数。
第二行是一个长度为的字符串，仅由"R、G、B"这三种字符组成。第i个字符用于描述第i个节点的颜色。
接下来的行，每行有两个正整数和，代表和节点有一条边连接。保证输入一定表示一棵树。
输出描述:
一个正整数，代表芭芭拉能冲刺的距离的最大值。
示例1
输入
5
RRGBG
1 2
2 3
3 4
4 5
输出
3
说明
这棵树是一条1-2-3-4-5的链，选择路径2-3-4-5即可。这样芭芭拉直接从2冲到5，冲刺距离为3。
注意1和2的颜色相同，所以芭芭拉并不能在1-2这条边上冲刺。
备注:
对于10%的数据，
对于20%的数据，树退化成了一条链。
对于20%的数据，所有点的颜色都相同。
对于100%的数据，
思路
dfs或者bfs
代码
#include <bits/stdc++.h>
typedef long long ll;
const ll mod = 1e9+7;
using namespace std;
namespace fastIO {
inline void input(int& res) {
char c = getchar();res = 0;int f = 1;
while (!isdigit(c)) { f ^= c == '-'; c = getchar(); }
while (isdigit(c)) { res = (res << 3) + (res << 1) + (c ^ 48);c = getchar(); }
res = f ? res : -res;
}
inline ll qpow(ll a, ll b) {
ll ans = 1, base = a;
while (b) {
if (b & 1) ans = (ans * base % mod +mod )%mod;
base = (base * base % mod + mod)%mod;
b >>= 1;
}
return ans;
}
}
using namespace fastIO;
const int N = 1e5+5;
int Case,n,x,y,ans;
char s[N];
int f[N];
vector<int> zr[N];
void dfs(int root,int t){
f[root]=0;
for(auto v:zr[root]){
if(v==t) continue;
dfs(v,root);
if(s[v]!=s[root]){
ans = max(ans,f[root]+f[v]+1);
f[root]=max(f[root],f[v]+1);
}
}
}
void solve(){
input(n);
scanf("%s",s+1);
for(int i=1;i<n;i++){
input(x),input(y);
zr[x].push_back(y);
zr[y].push_back(x);
}
dfs(1,0);
printf("%d",ans);
}
int main(){
Case=1;
//input(Case);
while(Case--){
solve();
}
return 0;
}
/*
5
RRGBG
1 2
2 3
3 4
4 5
*/
I 永远亭的小游戏
链接：https://ac.nowcoder.com/acm/contest/8755/I
题目描述
蓬莱山辉夜由于整天宅在家，整个人都已经变成了一只废neet姬了。于是，她找来了铃仙和因幡帝，来玩一个小游戏。
辉夜拿出一个长度为的数组，铃仙拿出一个长度为的数组，因幡帝拿出一个长度为的数组。
她们等概率的在各自的数组中取一个数。辉夜想知道这三个取出的数的乘积的期望是多少？
可以证明，这个期望一定是有理数，可以写成\frac{x}{y}
y
x
的形式。请输出这个分数对10^9+710
9
+7取模的值。
提示：分数\frac{x}{y}
y
x
对取模的值的意义是在区间里找到一个数满足对取模为。
提示2：本题输入数据较大，推荐使用scanf或更快的输入方式
输入描述:
第一行输入三个正整数，用空格隔开。分别代表辉夜、铃仙和因幡帝拿到的数组长度。
第二行输入个正整数，代表辉夜拿到的数组。
第三行输入个正整数，代表铃仙拿到的数组。
第四行输入个正整数，代表因幡帝拿到的数组。
数据范围：
输出描述:
最后乘积的期望对取模的值。
示例1
输入
2 2 2
1 2
1 1
2 4
输出
500000008
说明
三个人各取一个数的组合有以下8种：
112=2
114=4
112=2
114=4
212=4
214=8
212=4
214=8
(2+4+2+4+4+8+4+8)/8=36/8=4.5
最终的乘积期望是4.5，即9/2，由于(500000008*2)%1000000007=9，因此输出500000008
思路
sumasumbsumc/(nmk)
注意取余
思维题
代码
#include <bits/stdc++.h>
typedef long long ll;
const ll mod = 1e9+7;
using namespace std;
namespace fastIO {
inline void input(ll& res) {
char c = getchar();res = 0;int f = 1;
while (!isdigit(c)) { f ^= c == '-'; c = getchar(); }
while (isdigit(c)) { res = (res << 3) + (res << 1) + (c ^ 48);c = getchar(); }
res = f ? res : -res;
}
inline ll qpow(ll a, ll b) {
ll ans = 1, base = a;
while (b) {
if (b & 1) ans = (ans * base % mod +mod )%mod;
base = (base * base % mod + mod)%mod;
b >>= 1;
}
return ans;
}
}
using namespace fastIO;
const int N = 1e6 + 5;
ll Case,n,m,k,x,suma,sumb,sumc;
void solve(){
input(n),input(m),input(k);
for(int i=1;i<=n;i++){
input(x);
suma+=x;
suma%=mod;
}
for(int i=1;i<=m;i++){
input(x);
sumb+=x;
sumb%=mod;
}
for(int i=1;i<=k;i++){
input(x);
sumc+=x;
sumc%=mod;
}
printf("%lld",suma*sumb%mod*sumc%mod*qpow(n*m%mod*k%mod,mod-2)%mod);
}
int main(){
Case=1;
//input(Case);
while(Case--){
solve();
}
return 0;
}
J 芭芭拉冲鸭~（续）（待补）
链接：https://ac.nowcoder.com/acm/contest/8755/J
题目描述
芭芭拉这次来到了一棵字母树，这同样是一棵无根树，每个节点上面有一个小写字母。
芭芭拉想知道，自己从x冲刺到y，从x走到y收集所有字母，选择其中一部分字母组成一个回文串，这个回文串的最大长度是多少？
同样的，芭芭拉冲刺的时候是不能掉头的。
一共有q次询问。每次的询问是独立的（即本次收集字母不影响之后的询问，每次询问时字母都是未被收集状态）。
输入描述:
第一行有一个正整数。
接下来的行，每行输入两个正整数和，代表和之间有一条无向边相连。
接下来一行有一个长度为的字符串，字符串仅由小写字母构成。第个字符表示节点上的字母。
接下来一行是一个正整数，代表询问次数。
接下来的行，每行两个正整数和。
（保证输入一定是一棵树）
输出描述:
对应每次询问，输出一个正整数，代表回文串的最大长度。
示例1
输入
5
1 2
1 3
2 4
2 5
abcba
3
4 5
1 2
3 3
输出
3
1
1
说明
这棵树的构造如下：
对于第一个询问，芭芭拉冲刺的路径是4-2-5，收集的字母有两个b一个a，可以构建的最长回文串是"bab"，长度为3。
对于第二个询问，芭芭拉冲刺的路径是1-2，收集的字母有一个b一个a，可以构建的最长回文串是"a"（也可以是"b"），长度为1。
对于第三个询问，芭芭拉起点和终点都是3，所以站在原地不动，收集的字母有只有一个c，可以构建的最长回文串是"c"，长度为1。
K 玩具销售员
链接：https://ac.nowcoder.com/acm/contest/8755/K
题目描述
达达利亚是至冬国著名的玩具销售员。
有一天，他进货了个玩具，但里面有个次品。
每次检查他最多挑2个玩具出来进行检查。不过达达利亚慧眼如炬，他一眼就能看到次品的所在。
他想不超过次检查就把所有的次品挑出来，请问他是否可能做到这一点？
输入描述:
三个正整数、、，用空格隔开。
输出描述:
如果达达利亚能在k次检查中挑出所有的次品，输出"Yes"。
否则输出"No"。
（不要输出引号）
示例1
输入
3 3 1
输出
No
说明
一共3个玩具，全部是次品。达达利亚无论怎么挑选都无法在一次检查中成功挑完所有次品
示例2
输入
5 3 2
输出
Yes
说明
一共5个玩具，有3个次品。达达利亚第一次检查挑选一个次品和一个正品，第二次检查挑选两个次品，这样就挑完所有次品了。
思路
k题过的比a题少？
2*k和m作比较即可
手速题
代码
#include <bits/stdc++.h>
typedef long long ll;
const ll mod = 9999999967;
using namespace std;
namespace fastIO {
inline void input(int& res) {
char c = getchar();res = 0;int f = 1;
while (!isdigit(c)) { f ^= c == '-'; c = getchar(); }
while (isdigit(c)) { res = (res << 3) + (res << 1) + (c ^ 48);c = getchar(); }
res = f ? res : -res;
}
inline ll qpow(ll a, ll b) {
ll ans = 1, base = a;
while (b) {
if (b & 1) ans = (ans * base % mod +mod )%mod;
base = (base * base % mod + mod)%mod;
b >>= 1;
}
return ans;
}
}
using namespace fastIO;
const int N = 1e6 + 5;
int Case,n,m,k;
void solve(){
input(n),input(m),input(k);
int ans = 0;
if(m%2) ans = m/2 + 1;
else ans = m/2;
if(ans<=k) puts("Yes");
else puts("No");
}
int main(){
Case=1;
//input(Case);
while(Case--){
solve();
}
return 0;
}
上一篇： 粒子群算法的matlab实现
下一篇： 如何使用光盘做系统的具体步骤
推荐阅读
-
北京信息科技大学第十二届程序设计竞赛暨ACM选拔赛题解
-
2018年北京信息科技大学第十届程序设计竞赛暨ACM选拔赛 D 打篮球（java）
-
2018年北京信息科技大学第十届程序设计竞赛暨ACM选拔赛 C 颜料的混合（java）
-
2018年北京信息科技大学第十届程序设计竞赛暨ACM选拔赛--I郊游（数学题）
-
2018年北京信息科技大学第十届程序设计竞赛暨ACM选拔赛 E 233（java）
-
I-永远亭的小游戏（北京信息科技大学第十二届程序设计竞赛暨ACM选拔赛）
-
2018年北京信息科技大学第十届程序设计竞赛暨ACM选拔赛 F 扫雷（java）
-
2018年北京信息科技大学第十届程序设计竞赛暨ACM选拔赛 H-程序员的好印象【LIS】
-
2018年北京信息科技大学第十届程序设计竞赛暨ACM选拔赛 程序员的好印象
-
2018年北京信息科技大学第十届程序设计竞赛暨ACM选拔赛 C 颜料的混合 （计算几何）