牛客多校第六场记录

柔光的暖阳◎ 2021-10-29 12:20 262阅读 0赞

## A ##

*  题意: 垃圾分类
 *  思路: 模拟

除数要double不然会wa QAQ

## B ##

*  题意: 将2进制的ipv6地址转换成**最短的字典序最小的**标准格式(需要缩0)
 *  思路: 模拟,先转成16进制,再去掉前置0,最后遍历所有缩0情况,获得答案.

#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <string> #include <stdlib.h> #include <vector> #include <queue> #include <cmath> #include <stack> #include <map> #include <set> #define ll long long #define FOR(i,l,r) for(int i = l ; i <= r ;++i ) #define inf 1<<30 #define EPS (1e-9) #define ALL(T) T.begin(),T.end() #define lson(i) i<<1 #define rson(i) (i<<1|1) using namespace std; typedef pair<int,int> pii; char buf[1029]; char ox[110]; char ox2[110]; char ansStr[110]; void toOx(){ // 变成16进制 int idx = 0; int val = 0; int oidx = 0; while(idx<128){ val= (val<<1)+(buf[idx++]-'0'); val= (val<<1)+(buf[idx++]-'0'); val= (val<<1)+(buf[idx++]-'0'); val= (val<<1)+(buf[idx++]-'0'); if(val<10){ ox[oidx] = val+'0'; }else{ ox[oidx] = val-10+'a'; } oidx++; val = 0; } ox[oidx] = 0; oidx = 0; FOR(i,0,31){ ox2[oidx++] = ox[i]; } ox2[oidx] = 0; idx = oidx; oidx = 0; FOR(i,0,idx-1){ if(ox2[i]=='0'){ if(ox2[i+1]=='0'){ if(ox2[i+2]=='0'){ ox[oidx++] = ox2[i+3]; ox[oidx++] = ':'; i+=3; }else{ ox[oidx++] = ox2[i+2]; ox[oidx++] = ox2[i+3]; ox[oidx++] = ':'; i+=3; } }else{ ox[oidx++] = ox2[i+1]; ox[oidx++] = ox2[i+2]; ox[oidx++] = ox2[i+3]; ox[oidx++] = ':'; i+=3; } }else{ ox[oidx++] = ox2[i]; ox[oidx++] = ox2[i+1]; ox[oidx++] = ox2[i+2]; ox[oidx++] = ox2[i+3]; ox[oidx++] = ':'; i+=3; } } ox[oidx-1] = 0; // printf("%s\n%s\n",ox2,ox); } int cmp(string s1,string s2){ if(s1.length() == s2.length()){ return s1<s2; } return s1.length() <s2.length(); } vector<string> as; void ya0(){ // 压缩0 vector<pii > pos; int len = strlen(ox); pii lin; FOR(i,0,len-1){ if(ox[i]=='0'&&ox[i+1]==':'&&(i-1<0 ||ox[i-1]==':')){ lin.second = i; lin.first = 0; while(i+2<len&&ox[i+2]=='0'){ i+=2; lin.first++; } pos.push_back(lin); } } int idx= 0; sort(ALL(pos)); if(pos.size()==0 || pos[pos.size()-1].first==0){ FOR(i,0,len){ ansStr[i] = ox[i]; } as.push_back(ansStr); return ; } int tmp = pos[pos.size()-1].first; for(auto lin:pos){ if(lin.first!=tmp) continue; idx = 0; FOR(i,0,len-1){ if(i!=lin.second){ ansStr[idx++] = ox[i]; }else{ if(ansStr[idx-1]!=':') ansStr[idx++] = ':'; ansStr[idx++] = ':'; i += lin.first*2+1; } } ansStr[idx] = 0; // string tstr = ansStr; as.push_back(ansStr); } sort(ALL(as),cmp); } int main(){ int t; scanf("%d",&t); FOR(cas,1,t){ as.clear(); scanf("%s",buf); toOx(); ya0(); printf("Case #%d: ",cas); cout << as[0] << '\n'; } return 0; }

压中间的零和压首尾的零,字符串长度不一样. 直接遍历所有情况sort一遍即可

## D ##

*  题意: 有k个箱子,n个物品,每个物品有一个体积\\(a\_i\\). 对于每个箱子都要放到不能再放物品为止再去下一个箱子放.求最小的能放下所有物品的箱子容量
 *  思路: 从下界\\(\\frac\{\\sum\{a\_i\}\}\{n\}\\)开始枚举箱子的大小,multiset的upper\_bound(第一个大于的)来模拟放的过程

#include<bits/stdc++.h> #define ll long long #define FOR(i,l,r) for(int i = l ; i <= r ;++i ) #define inf 1<<30 #define EPS (1e-9) #define ALL(T) T.begin(),T.end() #define lson(i) i<<1 #define rson(i) (i<<1|1) using namespace std; const int maxn(1e4+5); int a[maxn],r,l; int n,k; void input(){ memset(a,0,sizeof(a)); scanf("%d%d",&n,&k); r = 0; FOR(i,1,n){ scanf("%d",&l); r += l; a[l]++; } r/=k; } multiset<int> s; int check(int mid){ s.clear(); for(int i=1;i<=1000;++i){ for(int j=1;j<=a[i];++j){ s.insert(i); } } for(int i=1;i<=k;++i){ int y = mid; while(y){ auto iter = s.upper_bound(y); if(iter != s.begin()){ --iter; y -=(*iter); s.erase(iter); }else{ break; } } } return s.size()==0; } int main(){ int t; scanf("%d",&t); FOR(cas,1,t){ input(); while(!check(r)){ r++; } printf("Case #%d: %d\n",cas,r); } return 0; }

这道题很容易想到二分,从而想到\\(O(n^2)\\)的\\(check()\\)\+\\(O(log(T))\\)的二分,但这种取值不连续的填满问题是不满足二分的性质的... 可以通过每次枚举一段区间来二分.  
有一道非常相似的题目U33405 纽约

## G ##

*  题意: 给出n个字母\\(A到J\\)的字符串,求是否有一个\\(0到9\\)的排列能将所有字符串映射为一个合法的日期且为星期五.
 *  思路: 先预处理出所有的排列,然后枚举通过蔡勒公式判断是否合法

## J ##

*  题意: 给出n\*m的矩阵,每列的元素要从后往前选,每行全选会得到一个奖励,求能获得的最大收益.
 *  思路: 枚举j列为所选最短的列(获得奖励),再枚举每一行的最大收益(从当前选到最后)

#include<bits/stdc++.h> #define ll long long #define FOR(i,l,r) for(int i = l ; i <= r ;++i ) #define inf 1<<30 #define EPS (1e-9) #define ALL(T) T.begin(),T.end() #define lson(i) i<<1 #define rson(i) (i<<1|1) using namespace std; typedef pair<int,int> pii; const int maxn = 1e4+10; ll c[maxn][maxn],d[maxn],mx[maxn][maxn],smx[maxn]; int n,m; int main(){ int t; scanf("%d",&t); FOR(cas,1,t){ scanf("%d%d",&n,&m); int x; FOR(i,1,n){ FOR(j,1,m){ scanf("%d",&x); c[i][j]=c[i][j-1]-x; } mx[i][m+1] = -1ll<<60; for(int j=m;j>=0;--j){ mx[i][j] = max(mx[i][j+1],c[i][j]); } } FOR(j,0,m){ smx[j] = 0; FOR(i,1,n){ smx[j] += mx[i][j]; } } ll ans = 0,D=0,sum; for(int j=0;j<=m;++j){ if(j) scanf("%d",&x),D+=x; sum = -1ll<<60; for(int i=1;i<=n;++i){ // if(c[i][j]-mx[i][j] > sum){ // sum = c[i][j] - mx[i][j]; // } sum = c[i][j] - mx[i][j] + smx[j]; ans = max(ans,sum+D); } // sum+= smx[j]; // for(int i=1;i<=n;++i) sum+= mx[i][j]; // ans = max(ans,sum+D); } printf("Case #%d: %lld\n",cas,ans); } return 0; }

转载于:https://www.cnblogs.com/xxrlz/p/11317414.html