本场总结：
A.签到
B.模拟
C.回文树
D.猜结论check
E.构造
G.全排列和蔡勒公式check----O(1) 判断星期几
J.前缀和dp
小结
----练构造
----回文树就是个**板子选手，还要再学
----构造想法
----学到了蔡勒公式
----练dp
A. Garbage Classification
大致题意：就不分析了，签到题.
#include<bits/stdc++.h>
using namespace std;
int vis[27];
char s1[2005],s2[27];
int main()
{
int t,opt=1;
cin>>t;
while( t-- )
{
cin>>(s1+1);
cin>>s2;
int num1=0,num2=0,num3=0;
int len=strlen(s1+1);
for( int i=1;i<=len;i++ )
{
int id=s1[i]-'a';
if( s2[id]=='d' ) num1++;
else if( s2[id]=='w' ) num2++;
else if( s2[id]=='h' ) num3++;
}
printf("Case #%d: ",opt++);
if( num3*4>=len ) puts("Harmful");
else if( num3*10<=len ) puts("Recyclable");
else if( num1>=num2*2 ) puts("Dry");
else puts("Wet");
}
} B. Shorten IPv6 Address
大致题意:给你一个128位的字符串.求缩短后的字符串.缩短的规则如下:每四位缩成一个字符,然后每四个字符打引号.输出的时候要去掉每一块中的前导0,并且如果有两个以上连续的块为0的话可以缩短为"::",但是只能缩一次,求长度最短的情况下字典序最小的字符串.
分析:直接模拟..可以直接删掉合理最长的并且位置最后的0段.
#include<bits/stdc++.h>
using namespace std;
const int maxn=200;
int b[10],c[10];
int main()
{
int t;
scanf("%d",&t);
for( int tt=1;tt<=t;tt++ )
{
for( int i=1;i<=8;i++ )
{
int x=0,s;
for( int j=1;j<=16;j++ )
{
scanf("%1d",&s);
x=x*2+s;
}
b[i]=x;
}
for( int i=1;i<=10;i++ ) c[i]=0;
c[0]=100;
int l=0;
for( int i=1;i<=8;i++ )
{
if( b[i]==0 ) l++;
else if( l>0 )
{
c[l]=i-l;
l=0;
}
}
if( l>0 && c[l]<=1 ) c[l]=8-l+1;
bool flag=0;
printf("Case #%d: ",tt);
for( int i=8;i>=2;i-- )
{
if( c[i]>0 )
{
for( int j=1;j<=8;j++ )
{
if( j==c[i] )
{
flag=1;
printf("::");
j=j+i-1;
}
else
{
printf("%x",b[j]);
if( j<8 && flag || ( !flag && (j+1) != c[i] ) ) printf(":");
}
}
puts("");
flag=1;
break;
}
}
if( !flag )
{
for( int i=1;i<=8;i++ )
{
printf("%x",b[i]);
if( i!=8 ) printf(":");
}
puts("");
}
}
} C.Palindrome Mouse
大致题意：给一个字符串，集合S是该字符串的回文串集合,求S集合中有多少对不同的字符串满足子集关系.
分析:回文树，对于每一个回文串能延伸的长度就是该回文串的贡献。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 300005 ;
const int N = 26;
const int mod=1e9+7;
struct PAM {
int next[MAXN][N] ;//表示编号为i的节点表示的回文串在两边添加字符c以后变成的回文串的编号（和字典树类似）
int fail[MAXN] ;//fail[i]表示
int cnt[MAXN] ; //表示节点i代表的字符串出节点i失配以后跳转到长度小于该串且以该节点表示回文串的最后一个字符结尾的最长回文串表示的节点出 现次数 ，最后count()函数跑一遍以后才是正确的）
int num[MAXN] ;//num[i]表示以节点i表示的最长回文串的最右端点为回文串结尾的回文串个数(即本质不同且包括本身)
int len[MAXN] ;//len[i]表示节点i表示的回文串的长度（一个节点表示一个回文串)
int S[MAXN] ;//存放添加的字符
int last ;//指向新添加一个字母后所形成的最长回文串表示的节点。
int n ;//表示添加的字符个数。
int p ;//表示添加的节点个数(本质不同的字符串总数)
int newnode ( int l ) {//新建节点
for ( int i = 0 ; i < N ; ++ i ) next[p][i] = 0 ;
cnt[p] = 0 ;
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 get_fail ( int x ) {//和KMP一样，失配后找一个尽量最长的
while ( S[n - len[x] - 1] != S[n] ) x = fail[x] ;
return x ;
}
void add ( int c ) {
c -= 'a' ;
S[++ n] = c ;
int cur = get_fail ( last ) ;//通过上一个回文串找这个回文串的匹配位置
if ( !next[cur][c] ) {//如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串
int now = newnode ( len[cur] + 2 ) ;//新建节点
fail[now] = next[get_fail ( fail[cur] )][c] ;//和AC自动机一样建立fail指针，以便失配后跳转
next[cur][c] = now ;
num[now] = num[fail[now]] + 1 ;
}
last = next[cur][c] ;
cnt[last] ++ ;
}
void count () {
for ( int i = p - 1 ; i >= 0 ; -- i ) cnt[fail[i]] += cnt[i] ;
//父亲累加儿子的cnt，因为如果fail[v]=u，则u一定是v的子回文串！
}
ll siz[MAXN],nu[MAXN];
int vis[MAXN];
void dfs( int x )
{
siz[x]=1;
nu[x]= ( vis[x]==0 ) + ( vis[fail[x]]==0 );
vis[x]++;vis[fail[x]]++;
for( int i=0;i<26;i++ )
{
int v=next[x][i];
if( !v ) continue;
dfs(v);
siz[x]+=siz[v];
}
vis[x]--;
vis[fail[x]]--;
}
ll get_ans()
{
memset(nu,0,sizeof(nu));
dfs(1);dfs(0);
ll ans=0;
for( int i=2;i<p;i++ ) ans+=( siz[i]*nu[i]-1);
return ans;
}
}pam;
int main()
{
int t,cas=1;
cin>>t;
while( t-- )
{
string s;
cin>>s;
pam.init();
for( int i=0;i<s.size();i++ ) pam.add(s[i]);
printf("Case #%d: %lld\n",cas++,pam.get_ans() );
}
}D. Move
大致题意：有n件物品，每件物品体积为vi，用k个相同大小的盒子来装他们，问盒子最小体积可以为多少。( k,n,vi<=1000 )
规定装箱策略：
每一次，他都会在下一个策略前把物品放进一个盒子里，然后再试着把另一个盒子装满。
对于每个箱子，他会将一个最大合适体积的未包装物品反复放入箱内，直到无法在盒子内装上这类物品为止。
分析：我们知道盒子最小体积为max(a[n],sum/k)，我们可以从最小可能的体积开始枚举，一个个来判断。数据都很小不超过1000显然不会T。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e3+10;
const ll inf=1ll<<60;
int a[maxn],n,m,b[maxn];
bool check( int x )
{
for( int i=1;i<=m;i++ ) b[i]=x;
for( int i=n;i>=1;i-- )
{
bool flag=0;
for( int j=1;j<=m;j++ )
{
if( a[i]<=b[j] )
{
b[j]-=a[i];
flag=1;
break;
}
}
if( flag==0 ) return false;
}
return true;
}
int main()
{
int t,opt=1;
cin>>t;
while( t-- )
{
int sum=0;
cin>>n>>m;
for( int i=1;i<=n;i++ )
{
cin>>a[i];
sum+=a[i];
}
sort(a+1,a+1+n);
for( int i=max(a[n],sum/m);;i++ )
{
if( check(i) )
{
printf("Case #%d: %d\n", opt++,i);
break;
}
}
}
return 0;
}E. Androgynos
大致题意：T组样例，每组案例一个整数 n ，表示有一个顶点数为 n 的图，问你这个图是否和他的补图同构，（也就是自同构）
分析:见题解：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2005;
int a[maxn][maxn],b[maxn];
void solve( int n )
{
memset(a,0,sizeof(a));
int len=n/2;
for( int i=1;i<=len;i++ ) // 块 1 块 2 全连通 并且 块1 块2 自连通
{
for( int j=1;j<i;j++ ) a[i][j]=a[j][i]=1;
}
for( int i=1;i<=len/2;i++ ) // 块 1 与 块 3 全连通
{
for( int j=len+1;j<=len/2+len;j++ ) a[i][j]=a[j][i]=1;
}
for( int i=len/2+1;i<=len;i++ ) // 块 2 与 块 4 全连通
{
for( int j=len+len/2+1;j<=n;j++ ) a[i][j]=a[j][i]=1;
}
for( int i=1;i<=len;i++ ) b[i]=len+i;
for( int i=len+1;i<=n;i++ ) b[i]=n-i+1;
}
void print( int n )
{
for( int i=1;i<=n;i++ )
{
for( int j=1;j<=n;j++ ) printf("%d",a[i][j]);puts("");
}
}
int main()
{
int t,cas=1;
scanf("%d",&t);
while( t-- )
{
int n;
scanf("%d",&n);
printf("Case #%d: ",cas++);
if( n%4==0 )
{
puts("Yes");
solve(n);
print(n);
printf("%d",b[1]);
for( int i=2;i<=n;i++ ) printf(" %d",b[i]);puts("");
}
else if( n%4==1 )
{
puts("Yes");
solve(n-1);
for( int i=1;i<=n/2;i++ ) a[n][i]=a[i][n]=1;
print(n);
for( int i=1;i<=n-1;i++ ) printf("%d ",b[i]);
printf("%d\n",n);
}
else puts("No");
}
}G. Is Today Friday?
**大致题意：:给你n个日期格式为yyyy/mm/dd的字符串,让你求一个长度为10的字符串，第i位的字母为i,求字典序最小的字符串以满足所有给出的字符串.日期要求，并且该天不为星期五.
分析：暴力，next_permutation枚举排列,然后check。判断星期几 用蔡勒公式。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
const int inf=0x3f3f3f3f;
vector<string> s;
int n,a[20];
bool flag;
int cal( int y,int m,int d ) // 蔡勒公式 O(1) 判断日期 星期几
{
if( m<=2 ) y--,m+=12;
int c=y/100; y%=100;
int week=( y+y/4+c/4-2*c+26*(m+1)/10+d-1)%7;
return (week+7)%7;
}
int get_id( char ch )
{
return ch-'A'+1;
}
bool check()
{
for( int i=0;i<s.size();i++ )
{
int y,m,d;
y=a[ get_id(s[i][0]) ]*1000+a[ get_id(s[i][1]) ]*100+a[ get_id(s[i][2]) ]*10+a[ get_id(s[i][3]) ];
m=a[ get_id(s[i][5]) ]*10+a[ get_id(s[i][6]) ];
d=a[ get_id(s[i][8]) ]*10+a[ get_id(s[i][9]) ];
if( y<1600 || m<=0 || m>=13 || d<=0 || d>=32 ) return false;
if( ( m==4 || m==6 || m==9 || m==11 ) && d==31 ) return false;
if( m==2 && d>28+( y%4==0 && ( y%100!=0 || y%400==0 ) ) ) return false;
if( cal(y,m,d)!=5 ) return false;
}
return true;
}
int main()
{
int t,cas=1;
cin>>t;
while( t-- )
{
s.clear();
flag=false;
cin>>n;
for( int i=1;i<=n;i++ )
{
string s1;cin>>s1;
s.push_back(s1);
}
sort(s.begin(),s.end());
s.erase( unique(s.begin(),s.end()),s.end() );
for( int i=1;i<=10;i++ )a[i]=i-1;
do{
if( check() )
{
flag=true;
break;
}
}while( next_permutation(a+1,a+11) );
printf("Case #%d: ",cas++);
if( flag )
{
for( int i=1;i<=10;i++ )printf("%d",a[i]);puts("");
}
else puts("Impossible");
}
}J. Upgrading Technology
大致题意：有n个技能，每个技能都有m个等级（一开始等级都为0），每升一级需要花费C(i,j)（只能一级一级升），如果每个技能都达到i级，可以得到di的利润。可以不升级利润为0,。问能得到的最大利润为多少。( n,m<=1000 )
分析：
我们可以用前缀和维护每个技能升级的最小花费，倒着更新一遍最小值。
然后把每个技能升级到i（可能是以上）所需的最小花费加起来，然后我们维护下每个等级利润d的前缀和，技能最小等级为i时的利润为d的前缀和.
每个技能升级到i所需的最小花费。这里要注意两个点，一是我们前面维护的每个技能升级到i（可能是以上）所需的最小花费可能把技能等级更新到了i以上，若每个技能等级都在i以上，那么获得的利润就不是d1~ i，而是当前最小技能j的利润和d1~j，所以我们需要保留一个升级到i所需花费与我们维护的最小值差最小的来确保最低等级为i且获得的利润最大。二是注意可能存在有技能等级为0，其他技能升级花费为负的情况.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1005;
const ll inf=1ll<<60;
ll a[maxn][maxn],b[maxn],c[maxn][maxn];
int main()
{
int t,opt=1;
cin>>t;
while( t-- )
{
memset(a,0,sizeof(a));
int n,m;
scanf("%d%d",&n,&m);
for( int i=1;i<=n;i++ )
{
for( int j=1;j<=m;j++ )
{
scanf("%lld",&a[i][j]);
a[i][j]+=a[i][j-1];
c[i][j]=a[i][j];
}
a[n+1][m]+=a[i][m];
for( int j=m-1;j>=0;j-- )
{
a[i][j]=min(a[i][j],a[i][j+1]);
a[n+1][j]+=a[i][j];
}
}
b[0]=0; // a[i][j] 第i棵技能树至少升级到 j 的最小花费
// a[n+1][j] 所有技能树至少升级的 j 的最小花费
// c[i][j] 第i棵技能树点升到j层技能的花费
// b[i] 所有技能树至少升级的 i 的收益
for( int i=1;i<=m;i++ )
{
scanf("%lld",&b[i]);
b[i]+=b[i-1];
}
ll ans=0; //要保留一个升级到i所需花费与我们维护的最小值差最小的
for( int i=0;i<=m;i++ ) //来确保最低等级为i且获得的利润最大
{
int pos=-1;
ll mind=inf,d;
for( int j=1;j<=n;j++ )
{
d=c[j][i]-a[j][i];
if( d<mind )
{
mind=d;
pos=j;
}
}
ans=max(ans,b[i]-a[n+1][i]+a[pos][i]-c[pos][i]);
}
printf("Case #%d: %lld\n",opt++,ans);
}
return 0;
} 
京公网安备 11010502036488号