这次牛客练习赛，都考了一点小技巧。
A 随便模拟一下
链接：https://www.nowcoder.com/acm/contest/156/A
来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
紧张刺激的世界杯正在进行中(在托米的世界线里)，欧洲人托米沉迷于***无法自拔。
托米的口袋里有 100 元，50元，20元，10元，5元，2元，1元的纸币，50分，20分，10分，5分，2分，1分的硬币各无限个。
托米计划买下几注 a 元 b 分的彩票，他希望能支出的纸票数量和硬币数量之和最小，他希望你帮助他完成这个任务。同时由于彩票亭不支持找零，托米希望他的支出恰好等于 a 元 b 分
输入描述:
第一行输入一个正整数 T下面 T 行每行两个整数 a,b 输出描述:
每行输出 13 个正整数 n1 ...n13, 对应题面顺序给出最小化支出纸票数量和硬币数量之和的情况下，每种货币的使用次数，如果有多种方案，输出字典序最大的一种，注意这里字典序是依次比较n1到n13，而不是简单的把 13 个正整数拼接在一起
示例1
输入
2
1 5
2 4 输出
0 0 0 0 0 0 1 0 0 0 1 0 0
0 0 0 0 0 1 0 0 0 0 0 2 0 备注:
T=100,0≤ a≤ 109, 0≤ b<100
#include<bits/stdc++.h>
using namespace std;
int a[7]= {100,50,20,10,5,2,1};
int b[6]= {50,20,10,5,2,1};
int a1[7],b1[6];
int main() {
int t;
scanf("%d",&t);
while(t--) {
int x,y;
cin>>x>>y;
for(int i=0; i<7; i++) {
a1[i]=x/a[i];
x=x%a[i];
}
for(int i=0; i<6; i++) {
b1[i]=y/b[i];
y%=b[i];
}
for(int i=0; i<7; i++) {
printf("%d%c",a1[i],' ');
}
for(int i=0; i<6; i++) {
printf("%d%c",b1[i],i==5?'\n':' ');
}
}
return 0;
}
B
链接：https://www.nowcoder.com/acm/contest/156/B
来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
欧洲人托米非常喜欢数字，他经常在空闲时玩下面的游戏
对于一个数字 n, 托米会随性选中一个数 p, (1 ＜ p <= n), 将 n 拆分成 ,v=n-u,并对 u,v 重复这个过程，直到他有了 n 个 1
1317 为了挑战托米，在每次托米进行划分时，会给托米奖励 u * v 的分数，托米希望你能帮他最大化他的得分。
输入描述:
第一行一个正整数 T下面 T 行每行一个正整数 n 输出描述:
对于每组数据，输出托米的最大得分
示例1
输入
1 5 输出
10 备注:
T≤ 104, n≤ 109 推公式
2 = 1*1
3 =1*2 +1*1;
4=1*3 +1*2+1*1;
规律就是 Sn = (n*(n-1))/2;
#include<bits/stdc++.h>
using namespace std;
long long n;
int main() {
int t;
scanf("%d",&t);
while(t--) {
scanf("%lld",&n);
printf("%lld\n",(n*(n-1))/2);
}
return 0;
}
C
链接：https://www.nowcoder.com/acm/contest/156/C
来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
托米完成了1317的上一个任务，十分高兴，可是考验还没有结束
说话间1317给了托米 n 个自然数 a1... an, 托米可以选出一些带回家，但是他选出的数需要满足一些条件
设托米选出来了k 个数 b1,b2... bk, 设这个数列 b 的给值为 b 中所有数按位与的结果，如果你能找到一个整除 b 的最大的 2v,(v≥ 0)， 则设定 v 为这个数列的给价，如果不存在这样的 v，则给价值为 -1, 1317 希望托米在最大化给价的情况下，最大化 k
输入描述:
第一行输入一个整数 n, 第二行输入 a1...an 输出描述:
第一行输出最大的整数 k, 第二行输出 k 个整数 b1... bk, 按原数列的相对顺序输出 (如果行末有额外空格可能会格式错误)
示例1
输入
5
1 2 3 4 5 输出
2
4 5 备注:
n≤ 105, a1... an < 231
题目毒瘤读了半天
给你一个 n 个数 a1 ...an,选几个数 b1...bk 然后全部&后 b=b1&b2...&bk, b&2^v==0, v最大就是当前选的这个b序列的值；
求 V最大的情况下K最大。
题解 ：从最高位为1 &到最低位是1 一路下来就行。v 的值是按位于之后最后一位为 1的位置。
#include<bits/stdc++.h>
using namespace std;
long long n;
typedef long long ll;
const int maxn=1e5+5;
ll a[maxn],x[maxn];
int main() {
scanf("%d",&n);
for(int i=0; i<n; i++) {
scanf("%lld",&a[i]);
}
for(int i=0; i<=31; i++) { //预处理下最高位位置的值
x[i]=1<<i;
}
int k=0,flag=0,bi=0;
ll v=0,m=-1;
for(int i=31; i>=0; i--) {//从最高为处理到最低位
int t=0;
flag=0;
for(int j=0; j<n; j++) {
if((a[j]&x[i])==x[i]) { //把高于最高位的值全部选上
if(t==0) {
flag=a[j];
} else {
flag&=a[j];
}
t++;
}
}
int pos=0;
while(flag>0&&(flag&1)==0) { //判断v 的位置
pos++;
flag>>=1;
}
if(pos>m||(pos==m&&t>k)) { //更新值
m=pos;
v=flag<<pos;
k=t;
}
}
printf("%d\n",k);
for(int i=0; i<n; i++) {
if((a[i]&v)==v) { //把所有能按位于成 v 的全部输出。
k--;
printf("%lld%c",a[i],k==0?'\n':' ');
}
}
return 0;
} 有点难懂，看不懂留言。
D
链接：https://www.nowcoder.com/acm/contest/156/D
来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
托米没有完成上一个任务，准备施展黑魔法推倒 1317
黑魔法咒语被描述为一个 长为 n 的，仅包含小写英文字母 'a'...'i' 的字符串，在托米所在的星球，魔法造成的每次有效伤害都是来自他的一个子序列，对于每一个 'a'... 'i' 的排列(共 9! 种)，若作为咒语的子序列出现, 就会造成 1 的伤害
而咒语的总伤害为所有 'a'... 'i' 的排列造成的伤害值之和，托米能打出多少点的伤害，是否能击败 1317 呢？
输入描述:
一行输入一个字符串 s 输出描述:
一行输出一个数，表示伤害值
示例1
输入
aabcdefghi 输出
1 备注:
|s| ≤ 3000 优雅的暴力。
全排列所有情况，二分查找这种情况在字符串里面可不可行，然后一个个加上。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=4e5+5;
char ch[maxn];
int n[maxn];
vector<int> v[10];
int dp[maxn][9];
int main() {
int ans[9]= {0,1,2,3,4,5,6,7,8};
int k=0;
do {
for(int i=0; i<9; i++) {
dp[k][i]=ans[i];
}
k++;
} while(next_permutation(ans,ans+9));
cin>>ch;
int l=strlen(ch);
for(int i=0; i<l; i++) {
n[i]=ch[i]-'a';
v[n[i]].push_back(i);
}
int res=0;
for(int i=0; i<k; i++) {
int p=-1;
for(int j=0; j<9; j++) {
int num=dp[i][j];
if(upper_bound(v[num].begin(),v[num].end(),p)==v[num].end()) {
break;
}
int t=upper_bound(v[num].begin(),v[num].end(),p)-v[num].begin();
p=v[num][t];
if(j==8) {
res++;
}
}
}
cout<<res<<endl;
return 0;
}
京公网安备 11010502036488号