A Garbage Classification
题意
给定一个字符串代表垃圾，26个字符每个字符代表某种组成成分，根据题意判断垃圾类别。
分析
温暖的签到题，注意别写成除法就行。
代码
#include <bits/stdc++.h>
using namespace std;
const int N=2050;
int T;
char s[N];
char let[30];
map<char,char> mp;
int main(void){
// freopen("in.txt","r",stdin);
scanf("%d",&T);
for(int cas=1;cas<=T;cas++){
scanf("%s",s);
scanf("%s",let);
mp.clear();
for(int i=0;i<26;i++){
mp['a'+i]=let[i];
}
int d=0,w=0,h=0;
int len=strlen(s);
for(int i=0;i<len;i++){
if(mp[s[i]]=='d'){
d++;
}else if(mp[s[i]]=='w'){
w++;
}else if(mp[s[i]]=='h'){
h++;
}
}
printf("Case #%d: ",cas);
if(4*h>=len){
printf("Harmful
");
}else if(10*h<=len){
printf("Recyclable
");
}else{
if(d>=2*w){
printf("Dry
");
}else{
printf("Wet
");
}
}
}
return 0;
}
B Shorten IPv6 Address
题意
给定一个128位的二进制数，先要转成32位十六进制数，每4位一组，中间用冒号分隔，然后如果一组都是0，那么4个0用1个0代替即可，然后可以选择一串且只能一串连续的0和冒号，替换成两个冒号，问可以得到的最小字典序是哪个。
分析
先构造出原字符串，然后对8个组，记录在字符串中的位置，然后枚举让每个组开头的连续0替换成双冒号后得到的字符串，直接暴力找出所有字符串，排序即可。
代码
#include <bits/stdc++.h>
using namespace std;
int T;
char s[130];
char hex(char a,char b,char c,char d){
int t=(a-'0')*8+(b-'0')*4+(c-'0')*2+(d-'0');
if(t<=9){
return char(t+'0');
}else{
return char(t-10+'a');
}
}
vector<string> vs;
bool cmp(string a,string b){
int al=a.size();
int bl=b.size();
if(al==bl){
return a<b;
}else{
return al<bl;
}
}
int idx[8];
int main(void){
// freopen("in.txt","r",stdin);
scanf("%d",&T);
for(int cas=1;cas<=T;cas++){
scanf("%s",s);
memset(idx,0,sizeof(idx));
string he="";
int cnt=0;
for(int i=0;i<128;i+=16){
string t="";
bool ac=false;
for(int j=i;j<i+16;j+=4){
char p=hex(s[j],s[j+1],s[j+2],s[j+3]);
if(!ac && p=='0'){
continue;
}
ac=true;
t+=p;
}
int q=he.size();
if(t==""){
he+="0";
}else{
he+=t;
}
idx[cnt++]=q;
if(i==112){
continue;
}
he+=":";
}
vs.clear();
vs.push_back(he);
int hes=he.size();
for(int i=0;i<8;i++){
string tle="";
int t=idx[i];
if(i!=0){
t--;
}
for(int j=0;j<t;j++){
tle+=he[j];
}
int mle=0;
while(t<hes && he[t]=='0' || he[t]==':'){
if(he[t]=='0'){
mle++;
}
t++;
}
if(mle>=2){
tle+="::";
}else{
int j=idx[i];
if(i!=0){
j--;
}
for(;j<t;j++){
tle+=he[j];
}
}
for(int j=t;j<hes;j++){
tle+=he[j];
}
vs.push_back(tle);
}
sort(vs.begin(),vs.end(),cmp);
printf("Case #%d: %s
",cas,vs[0].c_str());
}
return 0;
}
C Palindrome Mouse
题意
给定一个字符串，求多少对((a,b))满足(a)和(b)都是原串的回文子串，且(a)也是(b)的子串。
分析
-
先用回文树构造出所有回文子串节点，对于每个节点来说，对答案的贡献由两部分组成，一部分是fail指针，比如aaa的fail指向aa，那么aa就是aaa的子串，且因为都是树上节点，即都是回文，另一部分是next指针，比如bb的next指向abba，那么bb就是abba的子串，且可以看出bb的fail指针b应该也是abba的子串。
-
因此我们需要求出每个节点向上fail指针跳的次数和向下next指针跳的次数，乘法定理计算每个节点的贡献。
-
next次数的求法类似于dfs求子树大小，而在dfs的同时暴力往上求fail指针，为了避免重复计数，比如bb跳过的fail指针，bbbb不能再跳，需要暴力标记每个指针是哪个节点跳的，dfs完之后也是暴力清空标记。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+50;
int vis[N],ndp[N],fdp[N];
struct PT{
int next[N][26],fail[N],cnt[N],num[N],len[N];
int S[N],last,id[N],n,p;
int newnode(int l){
for(int i=0;i<26;i++){
next[p][i]=0;
}
cnt[p]=num[p]=0;
len[p]=l;
return p++;
}
void init(){
p=0;
newnode(0);
newnode(-1);
last=0;
n=0;
S[n]=-1;
fail[0]=1;
}
int getFail(int x){
while(S[n-len[x]-1]!=S[n]){
x=fail[x];
}
return x;
}
void add(int c){
c-='a';
S[++n]=c;
int cur=getFail(last);
if(!next[cur][c]){
int now=newnode(len[cur]+2);
fail[now]=next[getFail(fail[cur])][c];
num[now]=num[fail[now]]+1;
next[cur][c]=now;
}
last=next[cur][c];
cnt[last]++;
id[last]=n;
}
void count(){
for(int i=p-1;i>=0;i--){
cnt[fail[i]]+=cnt[i];
}
}
int dfs(int u){
ndp[u]=1;
fdp[u]=0;
//计算向上跳的fail指针次数，vis保证不重复(比如bb跳的fail指针，bbbb不能再跳)，>1保证不走到奇偶根
for(int t=u;!vis[t] && t>1;t=fail[t]){
vis[t]=u;
fdp[u]++;
}
for(int i=0;i<26;i++){
if(next[u][i]){
ndp[u]+=dfs(next[u][i]);
}
}
//清空标记
for(int t=u;vis[t]==u && t>1;t=fail[t]){
vis[t]=0;
}
return ndp[u];
}
ll solve(){
//从两个根dfs
dfs(0);
dfs(1);
ll ans=0;
for(int i=2;i<p;i++){
//除去根，每个节点的贡献(作为另一个回文子串的子串)为
//比如对于样例abba，回文节点bb的next指针指向abba，fail指针指向b
//因此ndp和fdp都为2，贡献为2*2-1=3
//即(b,bb) (b,abba) (bb,bb) (bb,abba)，减1就是要减掉本身
ans+=1ll*ndp[i]*fdp[i]-1;
}
return ans;
};
}ac;
int T;
char s[N];
int main(void){
// freopen("in.txt","r",stdin);
scanf("%d",&T);
for(int cas=1;cas<=T;cas++){
scanf("%s",s);
ac.init();
int len=strlen(s);
for(int i=0;i<len;i++){
ac.add(s[i]);
}
ac.count();
memset(vis,0,sizeof(vis));
printf("Case #%d: %lld
",cas,ac.solve());
}
return 0;
}
D Move
题意
(n)个物品，各自有体积(v_i)，要用(k)个箱子装，装的策略是贪心从大往小，能装就装，问每个箱子最小的容量。
分析
-
由于贪心的策略，使得箱子容量并不满足单调性，有可能小一点的容量可以，但是如果容量大一点，可能会先取装多个大的，导致小的太多刚好装不下。
-
最简单的做法是直接从容量的下界(max(v_n,(sum-1)/k+1))开始暴力枚举，然后用multiset判断。
-
上界的证明：
- 假设某个容量(V)装不下，那么每个箱子剩余容量都小于(maxV)
- 那么(k*(V-maxV+1)<=sum)
- 得到(V<=sum/k+maxV-1)
-
因为(v_i)的范围比较小，所以可以感性地理解一下，然后发现二分再暴力一段小区间也是可以的。
代码
#include <bits/stdc++.h>
using namespace std;
const int N=1005;
int T,n,k,a[N];
multiset<int> mt;
bool check(int x){
mt.clear();
for(int i=1;i<=n;i++){
mt.insert(a[i]);
}
for(int i=0;i<k;i++){
int u=0;
while(u<x && !mt.empty()){
auto p=mt.upper_bound(x-u);
if(p==mt.begin()){
break;
}
p--;
u+=*p;
mt.erase(p);
}
}
return mt.empty();
}
int main(void){
// freopen("in.txt","r",stdin);
scanf("%d",&T);
for(int cas=1;cas<=T;cas++){
scanf("%d%d",&n,&k);
int sum=0;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
sum+=a[i];
}
sort(a+1,a+1+n);
//从下界暴力枚举
int ans;
for(int v=max(a[n],(sum-1)/k+1);;v++){
if(check(v)){
ans=v;
break;
}
}
printf("Case #%d: %d
",cas,ans);
}
return 0;
}
G Is Today Friday?
题意
给n个日期字符串，A到J代表0到9的一个排列，求一个字典序最小的排列使得这n个日期都是星期五。
分析
-
因为有星期五这个限制，所以对前几个日期，先暴力全排列，找出满足条件的全排列，再从这些全排列中对剩下的日期进行判断。
-
根据日期计算周几可以用蔡勒公式或者基姆拉尔森公式
代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+50;
int T,n;
struct node{
char str[12];
bool operator<(const node& rhs)const{
return string(str)<string(rhs.str);
}
bool operator==(const node& rhs)const{
return string(str)==string(rhs.str);
}
}s[N];
vector<int> mp;
vector<vector<int> > ts;
int ms[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
bool leap(int y){
return ((y%4==0 && y%100!=0) || y%400==0);
}
//判断日期合法性
bool check(int y,int m,int d){
if(m==0 || m>12 || d==0){
return false;
}
int t=ms[m];
if(leap(y) && m==2){
t++;
}
return d<=t;
}
//基姆拉尔森公式
bool cl(int y,int m,int d){
if(!check(y,m,d)){
return false;
}
//题面...
if(y<1600){
return false;
}
//1 2月要转成上一年13 14月
if(m<=2){
m+=12;
y--;
}
int w=((d+2*m+3*(m+1)/5+y+y/4-y/100+y/400+1)%7+7)%7;
return w==5;
}
int main(void){
// freopen("in.txt","r",stdin);
scanf("%d",&T);
for(int cas=1;cas<=T;cas++){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%s",s[i].str);
}
printf("Case #%d: ",cas);
sort(s+1,s+1+n);
int nn=unique(s+1,s+1+n)-s-1;
//先根据前几个日期筛选出满足条件的全排列(不多)，再代入剩下的日期判断
//ts记得清空
ts.clear();
mp.clear();
for(int i=0;i<10;i++){
mp.push_back(i);
}
do{
bool ac=true;
//前4个
for(int i=1;i<=min(nn,4);i++){
int y=mp[s[i].str[0]-'A']*1000+mp[s[i].str[1]-'A']*100+mp[s[i].str[2]-'A']*10+mp[s[i].str[3]-'A'];
int m=mp[s[i].str[5]-'A']*10+mp[s[i].str[6]-'A'];
int d=mp[s[i].str[8]-'A']*10+mp[s[i].str[9]-'A'];
if(!cl(y,m,d)){
ac=false;
break;
}
}
if(ac){
ts.push_back(mp);
}
}while(next_permutation(mp.begin(),mp.end()));
//判断剩下n-4个
int sz=ts.size();
// for(int i=0;i<sz;i++){
// for(int j=0;j<10;j++){
// printf("%d",ts[i][j]);
// }
// printf("
");
// }
//考虑nn<=4的情况
if(nn<=4){
if(sz){
for(int i=0;i<10;i++){
printf("%d",ts[0][i]);
}
printf("
");
}else{
printf("Impossible
");
}
continue;
}
bool ok=false;
for(int i=0;i<sz;i++){
bool ac=true;
for(int j=5;j<=nn;j++){
int y=ts[i][s[j].str[0]-'A']*1000+ts[i][s[j].str[1]-'A']*100+ts[i][s[j].str[2]-'A']*10+ts[i][s[j].str[3]-'A'];
int m=ts[i][s[j].str[5]-'A']*10+ts[i][s[j].str[6]-'A'];
int d=ts[i][s[j].str[8]-'A']*10+ts[i][s[j].str[9]-'A'];
if(!cl(y,m,d)){
ac=false;
break;
}
}
if(ac){
for(int j=0;j<10;j++){
printf("%d",ts[i][j]);
}
printf("
");
ok=true;
break;
}
}
if(!ok){
printf("Impossible
");
}
}
return 0;
}
J Upgrading Technology
题意
(n)个技能，每个技能有(m)个等级，第(i)技能从(j-1)级升到(j)级需要花费(c_{ij})，(n)个技能都升到(i)级可以获得收益(d_i)，问最大收益。
分析
题意中暗示可以(O(nm))的复杂度，因此考虑枚举所以技能同时升到(i)级，此时的收益可以前缀和求出，再枚举最低等级也就是刚好(i)级的技能，那么这个技能的花费也能前缀和求出，而其他技能就可以在(i)级后面随便升了，我们只需要预处理出每个技能在某个级别之后升级的最小花费以及n个技能的最小花费和。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1005;
int T,n,m;
ll c[N][N],d[N];
ll dp[N],cp[N][N];
ll mn[N][N],smn[N];
int main(void){
freopen("in.txt","r",stdin);
scanf("%d",&T);
for(int cas=1;cas<=T;cas++){
ll ans=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
cp[i][0]=0;
for(int j=1;j<=m;j++){
scanf("%lld",&c[i][j]);
cp[i][j]=cp[i][j-1]+c[i][j];
}
}
//mn[i][j]表示第i个技能从第j个等级开始的最小前缀和
memset(smn,0,sizeof(smn));
for(int i=1;i<=n;i++){
mn[i][m]=cp[i][m];
ll _mn=mn[i][m];
smn[m]+=cp[i][m];
for(int j=m-1;j>=0;j--){
if(cp[i][j]<_mn){
_mn=cp[i][j];
}
mn[i][j]=_mn;
smn[j]+=mn[i][j];
}
}
dp[0]=0;
for(int i=1;i<=m;i++){
scanf("%lld",&d[i]);
dp[i]=dp[i-1]+d[i];
}
for(int i=0;i<=m;i++){
//枚举相同等级，可以都不升级
for(int j=1;j<=n;j++){
ll tmp=dp[i];
//枚举最低等级的技能
tmp-=cp[j][i];
//剩下的技能找大于等于i级别的最小前缀和之和
tmp-=smn[i];
//最低等级的技能被重复减了
tmp+=mn[j][i];
ans=max(ans,tmp);
}
}
printf("Case #%d: %lld
",cas,ans);
}
return 0;
}