目录
- 牛客NC16783 拼数
- cf489C Given Length and Sum of Digits...
- 牛客NC16618 排座椅
- 牛客NC200190 矩阵消除游戏
- 牛客NC16561 国王的游戏
- 牛客NC25043 Protecting the Flowers
- 牛客NC18979 毒瘤xor
- 牛客NC20860 兔子的区间密码
- 牛客NC17857 起床困难综合症
牛客NC16783 拼数
题意：将多个整数拼接成最大整数
思路：一开始直接想到的就是按字典序排序，仔细思考后发现没有那么简单，听了老师的课才想到可以把两个字符串先拼接起来再交换比较大小
也可以理解为，对于最优解字符串，相邻字符拼接起来一定是比两者交换后的结果大，同时不相邻的两字符串也满足（局部最优选择导向全局最优），故逆向的推出最优解的条件。
#include <bits/stdc++.h>
using namespace std;
int n;
string s[30];
bool cmp(string a,string b){
string s1 = a + b;
string s2 = b + a;
return s1 > s2;
}
signed main(){
scanf("%d",&n);
for (int i=1;i<=n;i++) cin>>s[i];
sort(s+1,s+1+n,cmp);
for (int i=1;i<=n;i++) cout<<s[i];
}
cf489C Given Length and Sum of Digits...
题意：给定数字长度和数字每位加起来的总和，求最小数和最大数
思路一： 一开始想到的是对s进行分类讨论，小于等于9的是一类，大于9的是另一类，然后模拟时对最大数而言，最高位要放尽可能多的9，对最小数而言，则是末尾要放尽可能多的9，此时其实已经想到可以先求出最大数，再将其翻转求最小数，但是觉得麻烦作罢（事实证明这才是正解），于是我开始了漫长又虐心的分类讨论之路。。
#include <bits/stdc++.h>
using namespace std;
signed main(){
int m,s;cin>>m>>s;
if (s==0){//特判s等于0的情况
if (m>1) cout<<-1<<" "<<-1;
else {
cout<<0<<" "<<0;
}
return 0;
}
int cnt = s / 9;//最多可以放几个9
int snt = s - (cnt*9);//剩余数的和
if (cnt>m){//特判放不满的情况
cout<<-1<<" "<<-1;
return 0;
}
string a(110,'0');
string b(110,'0');
if (s<=9){//分类讨论
if (m==1){
a[0] = char('0'+s);
}
else {
a[0] = '1';
for (int i=1;i<m-1;i++){
a[i] = '0';
}
a[m-1] = char(s-1+'0');
}
b[0] = char(s+'0');
for (int i=1;i<m;i++){
b[i] = '0';
}
}
else {
for (int i=1;i<=cnt;i++){
a[m-i] = '9';
}//末尾放9
if (m-cnt-1>=1){//处理放完9之后的数 分类讨论还有几位可以放
if (snt==0){//如果余数等于0 就要凑一个8出来
//比如 000999 100899
a[m-cnt] = '8';
for (int i=1;i<m-cnt;i++) a[i] = '0';
a[0] = '1';
}
else {//不为0直接放
a[m-cnt-1] = char('0'+snt-1);
for (int i=1;i<m-cnt-1;i++) a[i] = '0';
a[0] = '1';
}
}
else if (snt){//只剩一位直接放余数
a[0] = char('0'+snt);
}
for (int i=0;i<cnt;i++){
b[i] = '9';
}
b[cnt] = char('0'+snt);
for (int i=cnt+1;i<m;i++){
b[i] = '0';
}
}
int sum1 = 0,sum2 = 0;
for (int i=0;i<m;i++){
sum1 += (a[i]-'0');
sum2 += (b[i]-'0');
}
if ((sum1!=s)||(sum2!=s)){
cout<<-1<<" "<<-1<<endl;
return 0;
}
for (int i=0;i<m;i++) cout<<a[i];
cout<<" ";
for (int i=0;i<m;i++) cout<<b[i];
}
思路二：求出最大数后，直接翻转，特判首位是否为0，为0就对其+1，对最高位不是0的数-1
#include <bits/stdc++.h>
using namespace std;
signed main(){
int m,s;cin>>m>>s;
if (s==0){
if (m>1){
cout<<-1<<" "<<-1;
}
else {
cout<<0<<" "<<0;
}
return 0;
}
int cnt = s / 9;
int snt = s - cnt * 9;
if (cnt>m){
cout<<-1<<" "<<-1;
}
else if (cnt==m&&snt){
cout<<-1<<" "<<-1;
}
else {
string a,b;
for (int i=0;i<cnt;i++) b += '9';//高位放9
if (snt) b += char(snt+'0'),cnt++;//这边记得cnt要加1
for (;b.size()<m;) b += '0';//末尾补0
a = b;
reverse(a.begin(),a.end());
if (a[0]=='0'){
a[0] = '1';
a[m-cnt] -= 1;//修改
}
cout<<a<<" "<<b;
}
}
反思：WA了整整三四次才过的。第一是没有特判不能构造的情况，第二是在构造最小数的时候翻改了很多次，第三也是第一思路太过繁琐。。
牛客NC16618 排座椅
题意：给一系列相邻坐标，问怎样划分能最多将这些相邻坐标划分开来
思路：一开始无从下手，后来意识到横纵坐标其实是相互独立，那么就只要标记每一个横竖出现的次数，进行排序然后贪心的选择即可。
#include <bits/stdc++.h>
using namespace std;
int n,m,k,l,d;
struct Node{
int wi;
int pos;
};
Node x[2100],y[2100];
bool cmp(Node a,Node b){
return a.wi > b.wi;
}
bool cmp1(Node a,Node b){
return a.pos < b.pos;
}
signed main(){
cin>>n>>m>>k>>l>>d;
for (int i=0;i<=2001;i++){
x[i].pos = i;
y[i].pos = i;
}
while (d--){
int xx,yy,xi,yi;cin>>xx>>yy>>xi>>yi;
if (xx==xi){
y[min(yy,yi)].wi++;
}
else {
x[min(xx,xi)].wi++;
}
}
sort(y,y+2001,cmp);
sort(x,x+2001,cmp);
sort(y,y+l,cmp1);
sort(x,x+k,cmp1);
for (int i=0;i<k;i++) {
if (i) cout<<' ';
cout<<x[i].pos;
}
cout<<'\n';
for (int i=0;i<l;i++) {
if (i) cout<<' ';
cout<<y[i].pos;
}
cout<<'\n';
}
反思： 题意没看清要对输出进行排序，WA了好几发才过。。。
牛客NC200190 矩阵消除游戏
题意：给n行m列矩阵，每次可以选择一行或者一列消除，一共可以消除k次，问最多可以消除数的总和
思路：第一想法无脑排序，然后发现问题没有那么简单，尝试分类讨论，无果。。然后注意到数据范围，先暴力枚举怎么选择行数，再对列进行排序（一开始用dfs超时，最后用位运算思想过的）
超时代码：
//剪枝也可写 但是我还不会。。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,k,ans;
int a[20][20],b[20][20];
int dp[20];
bool vis[20];
void dfs(int step,int c){
if (step==n||c==k){
int sum = 0,cnt = 0,snt = 0;
memcpy(b,a,sizeof(a));
int h[20]={0};
for (int i=1;i<=n;i++){
printf("dp[%d] = %d\n",i,dp[i]);
if (!dp[i]) continue;
cnt++;
for (int j=1;j<=m;j++){
sum += b[i][j];
b[i][j] = 0;
}
}
//printf("sum = %d\n",sum);
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
h[j] += b[i][j];
}
}
sort(h+1,h+1+m,greater<int>());
for (int i=1;i<=k-cnt;i++){
sum += h[i];
}
ans = max(sum,ans);
return;
}
for (int i=step;i<=n;i++){
if (vis[i]) continue;
vis[i] = 1;
for (int j=0;j<2;j++){
if (j==0){
dp[i] = j;
dfs(step+1,c);
}
else if (c+1<=k){
dp[i] = j;
dfs(step+1,c+1);
dp[i] = 0;
}
}
vis[i] = 0;
}
}
signed main(){
cin>>n>>m>>k;
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
cin>>a[i][j];
}
}
dfs(1,0);
cout<<ans;
}
bitset:
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,k,ans;
int a[20][20],b[20][20];
int dp[20];
bool vis[20];
void solve(int x){
int t = 0,cnt = 0;
memset(dp,0,sizeof(dp));
while (x>0){
t++;
if (x&1) dp[t] = 1,cnt++;
else dp[t] = 0;//这边不小心把分号写成逗号，一直死循环（捂脸
x >>= 1;
}
//for (int i=1;i<=n;i++) printf("dp[%d] = %d\n",i,dp[i]);
if (cnt<=k){
int sum = 0,snt = 0;
memcpy(b,a,sizeof(a));
int h[20]={0};
for (int i=1;i<=n;i++){
//printf("dp[%d] = %d\n",i,dp[i]);
if (!dp[i]) continue;
//cnt++; 这边cnt++没备注 导致后面有几个点一直没过。。
for (int j=1;j<=m;j++){
sum += b[i][j];
b[i][j] = 0;
}
}
//printf("sum = %d\n",sum);
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
h[j] += b[i][j];
}
}
sort(h+1,h+1+m,greater<int>());
for (int i=1;i<=k-cnt;i++){
sum += h[i];
}
ans = max(sum,ans);
return;
}
}
signed main(){
cin>>n>>m>>k;
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
cin>>a[i][j];
}
}
for (int i=0;i<=((1<<n)-1);i++){
solve(i);
}
cout<<ans;
}
反思：修改代码要再检查一遍，然后以后对dfs还要再练习
牛客NC16561 国王的游戏
题意：经典贪心题（因为都是中文懒得概括了（x
思路：通过假设最优解列出相关公式，发现左右手乘积值排序后是最优解 （详细思路以后再补
#include <bits/stdc++.h>//这个代码只能得六十，因为题目数据范围需要开高精度
#define int long long
using namespace std;
int n,a,b,ans;
struct Node{
int l,r,w;
};
Node x[1100];
bool cmp(Node u,Node v){
return u.w < v.w;
}
signed main(){
scanf(" %lld",&n);
scanf(" %lld%lld",&x[0].l,&x[0].r);
for (int i=1;i<=n;i++){
scanf(" %lld%lld",&x[i].l,&x[i].r);
x[i].w = x[i].l * x[i].r;
}
sort(x+1,x+1+n,cmp);
int cnt = 1;
for (int i=1;i<=n;i++){
cnt = cnt * x[i-1].l;
ans = max(ans,cnt/x[i].r);
}
cout<<ans;
}
反思：通过交换寻找贪心的最优策略是常见套路
牛客NC25043 Protecting the Flowers
题意：有n头牛，回它所在的牛棚单程所用时间是ti,在花田等待时会对花田单位时间内破坏di的花，问怎样安排顺序时得对花田破坏最小
思路：和上题同理推出贪心策略公式 t[a]*d[b] < t[b] * d[a]
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 7;
struct Node{
int t,d;
}a[N];
int n,ans,sum;
bool cmp(Node u,Node v){
return u.t * v.d < v.t * u.d;
}
signed main(){
scanf(" %lld",&n);
for (int i=1;i<=n;i++){
scanf(" %lld%lld",&a[i].t,&a[i].d);
}
sort(a+1,a+1+n,cmp);
for (int i=1;i<=n;i++){
ans += a[i].d * sum;
sum += a[i].t * 2;
}
cout<<ans;
}
牛客NC18979 毒瘤xor
题意：略
思路：发现答案数字的二进制决策取决于所选区间数每位0，1的个数，故用前缀和维护 （不能无脑开long long ，会mle
#include <bits/stdc++.h>
using namespace std;
int n,q;
const int N = 1e5 + 7;
int a[N],sum[N][60],ans[60];
void dig(int t,int x){
for (int i=0;i<40;i++){
sum[t][i] = sum[t-1][i] + ((x&(1<<i))==0?0:1);
}
return;
}
void query(int l,int r){
int cnt = 0;
for (int i=0;i<31;i++){
int len = sum[r][i] - sum[l-1][i];
//cout<<len<<endl;
if(len<r-l+1-len){
cnt += (1<<i);
}
}
printf("%d\n",cnt);
return;
}
signed main(){
scanf(" %d",&n);
for (int i=1;i<=n;i++) scanf(" %d",a+i),dig(i,a[i]);
scanf(" %d",&q);
while (q--){
int l,r;scanf(" %d%d",&l,&r);
query(l,r);
}
}
牛客NC20860 兔子的区间密码
题意：给定区间任选两个数求最大异或值
思路：一开始把最大值固定住，变换最小值，很快想到要找第一位不同的，但没想到最大值也可以调，于是想了很久还是错的；最后才意识到找到第一位不同后，最大和最小值都可以进行调整并凑出一，故答案：(1<<pos)-1
}#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
int n;scanf(" %lld",&n);
while (n--){
int x,y;scanf(" %lld%lld",&x,&y);
if (x==y){
printf("%lld\n",(x^y));
}
else {
int pos,ans;
for (int i=0ll;;i++){
if ((x>>i)==(y>>i)){
pos = i;
break;
}
}
ans = (1ll<<pos)-1ll;(1后面加ll转换成长整型
cout<<ans<<endl;
}
}
}
牛客NC17857 起床困难综合症
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
string op[N];
int t[N];
signed main(){
int n,m;scanf(" %d%d",&n,&m);
int a = 0,b = (1<<29) - 1;
for (int i=0;i<n;i++){
cin>>op[i]>>t[i];
if (op[i]=="AND") a &= t[i],b &= t[i];
if (op[i]=="OR") a |= t[i],b |= t[i];
if (op[i]=="XOR") a ^= t[i],b ^= t[i];
}
bool ok = 0;
int ans = 0;
for (int i=29;i>=0;i--){
int x = 1 << i;
if ((a&x)!=0) continue;
if ((b&x)!=0&&ans+x<=m){
ans += x;
}
}
for (int i=0;i<n;i++){
if (op[i]=="AND") ans &= t[i];
if (op[i]=="OR") ans |= t[i];
if (op[i]=="XOR") ans ^= t[i];
}
cout<<ans;
}
京公网安备 11010502036488号