总结：
B.字典树和暴力
D.构造题
E.建最大生成树
F.树链剖分
H.二分答案和树上dfs
K.二分图和二进制枚举
小结：
----构造难顶，还要多搞搞
----练习最大生成树
----终于遇到一道icpc树链剖分，熟悉了一下线段树推标记
----二分答案
----二分图练得少，运用好多啊，还能判奇偶环....
B. Prefix Code
大致题意:给n个字符串，判断是否可以根据字符串前缀进行识别所有字符串。
分析：字典树和map暴力都行,给的字符串长度最多10,首先所有字符串有相同的肯定输出 No, map暴力处理出每个字符串的前缀判断是否出现过.
#include<bits/stdc++.h>
using namespace std;
map<string,int> mp;
int main()
{
int t,cas=1;
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>t;
while( t-- )
{
int n,flag=0;
cin>>n;
mp.clear();
vector<string> p;
for( int i=1;i<=n;i++ )
{
string s;
cin>>s;
p.push_back(s);
if( mp.count(s) ) flag=1;
else mp[s]++;
}
if( flag )
{
printf("Case #%d: ",cas++);
puts("No");
continue;
}
for( int i=0;i<p.size();i++ )
{
for( int j=0;j<p[i].size()-1;j++ )
{
string s2=p[i].substr(0,j+1);
if( mp.count(s2) )
{
flag=1;
break;
}
}
}
printf("Case #%d: ",cas++);
if( flag )
{
puts("No");
continue;
}
else puts("Yes");
}
}字典树：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int tree[maxn][11],cnt;
int tag[maxn];
bool add( char *s )
{
int len=strlen(s),root=0;
bool flag=0;
for( int i=0;i<len;i++ )
{
int x=s[i]-'0';
if( i==len-1 && tree[root][x] ) flag=true;
if( !tree[root][x] ) tree[root][x]=++cnt;
root=tree[root][x];
if( tag[root] ) flag=true;
}
tag[root]=true;
return flag;
}
int main()
{
int t,cas=1;
scanf("%d",&t);
while( t-- )
{
int n;
scanf("%d",&n);
int flag=0;
memset(tree,0,sizeof(tree));
memset(tag,0,sizeof(tag));
cnt=0;
char s[11];
for( int i=1;i<=n;i++ )
{
scanf("%s",s);
if( add(s) ) flag=1;
}
printf("Case #%d: ",cas++);
if( flag ) puts("No");
else puts("Yes");
}
return 0;
}
D. Spanning Tree Removal
大致题意: 给一个n阶完全图,请尽可能构造多的边互异的生成树.
分析:构造题， 我还特意搜了完全图中生成树的，发现有好多论文。 这个只能盲猜推结论构造了.
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t,cas=1;
scanf("%d",&t);
while( t-- )
{
int n;
scanf("%d",&n);
printf("Case #%d: %d\n",cas++,n/2);
for( int i=1;i<=n/2;i++ )
{
int l=i;
int r=(l+n-2)%n+1;
for( int j=1;j<n;j++ )
{
printf("%d %d\n",l,r);
if( j&1 ) l=l%n+1;
else r=(r+n-2)%n+1;
}
}
}
return 0;
}E. Cave Escape
大致题意：n * m单元格，给定起点坐标和终点坐标。还有每个位置权值的计算方式,从起点走到终点，第一次经过的位置可以获得一个能量，能量的计算方式是上一个位置的权值乘以当前位置的权值，求获得最大能量数.
分析：显然就是求一颗最大生成树。这里有个技巧就是存边索引可以是边权大小进行分类。（ val<10000 ）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+10;
int fa[maxn];
int sr,tr,sc,tc;
int v[1005][1005];
int x[maxn],a,b,c,p;
int n,m,t;
vector< pair<int,int> > e[10005];
int Find( int x )
{
return fa[x]==x ? x : fa[x]=Find(fa[x]);
}
void add( int x,int y ,int z )
{
e[z].push_back( make_pair( x,y ) );
}
int main()
{
int cas=1;
scanf("%d",&t);
while( t-- )
{
for( int i=0;i<=10000;i++ ) e[i].clear();
scanf("%d%d%d%d%d%d",&n,&m,&sr,&sc,&tr,&tc);
scanf("%d%d%d%d%d%d",&x[1],&x[2],&a,&b,&c,&p);
for( int i=3;i<=n*m;i++ ) x[i]=(a*x[i-1]+b*x[i-2]+c)%p;
for( int i=1;i<=n;i++ )
{
for( int j=1;j<=m;j++ )
{
fa[(i-1)*m+j]=(i-1)*m+j;
v[i][j]=x[(i-1)*m+j];
}
}
for( int i=1;i<=n;i++ )
{
for( int j=1;j<=m;j++ )
{
int now=(i-1)*m+j ,nex1=i*m+j, nex2=(i-1)*m+j+1;
if( i+1<=n ) add( now,nex1,v[i][j]*v[i+1][j]);
if( j+1<=m ) add( now,nex2,v[i][j]*v[i][j+1]);
}
}
ll ans=0;
int cnt=0;
for( int i=10000;i;i-- )
{
for( auto it:e[i] )
{
if( cnt==n*m-1 ) break;
int u1=it.first,v1=it.second;
int uu=Find(u1), vv=Find(v1);
if( uu==vv ) continue;
fa[uu]=fa[vv];
ans+=i;
cnt++;
}
if( cnt==n*m-1 ) break;
}
printf("Case #%d: %lld\n",cas++,ans);
}
return 0;
} F. A Simple Problem On A Tree
大致题意:给定树上n个结点和n-1条边,每个点都有权值,对结点有四种操作.
- 1 u v w 将编号为[u,v]的点权该为w
- 2 u v w 将编号为[u,v]的点权加上w
- 3 u v w 将编号为[u,v]的点权乘上w
- 4 u v w 对编号[u,v]的点权的三次方求和输出.
分析：很显然是一道树链剖分题(线段树推标记) 大胖题.有四种操作.考线段树 乘法、覆盖、累加 推标记.
三次方的标记变化具体看代码注释.
#include<bits/stdc++.h>
#define ls cur<<1
#define rs cur<<1|1
using namespace std;
const int maxn=1e5+10;
const int mod=1e9+7;
typedef long long ll;
//*/ 建边
struct node{
int to,next;
}edge[maxn<<2];
int tot,head[maxn];
void add( int u,int v )
{
edge[tot]={v,head[u]};
head[u]=tot++;
}
void init()
{
memset(head,-1,sizeof(head));
tot=0;
}
int rk[maxn]; // [线段树编号] 对 应结点号 结点初始赋值数组
ll val[maxn];
//*/ 线段树维护
struct node1{
int l;
int r;
ll sum1,sum2,sum3,mul,lazy;
}t[maxn<<2];
void pushup( int cur ) //ok
{
t[cur].sum1=( t[ls].sum1+t[rs].sum1 )%mod;
t[cur].sum2=( t[ls].sum2+t[rs].sum2 )%mod;
t[cur].sum3=( t[ls].sum3+t[rs].sum3 )%mod;
}
// x^3 --> ( x+z )^3 = x^3+3*x^2*z+3*x*z^2+z^3
// x^3 --> (ax)^3
// x^2 --> (x+z)^2 = ( x^2+2*x*z+z^2 )
// x^2 --> (ax)^2
void cal( int cur,ll x,ll y )
{
ll len=1ll*( t[cur].r-t[cur].l+1 );
ll a3=((x*x)%mod)*x%mod, a2=((3ll*x)%mod*x%mod)*y%mod, a1=(((3ll*x)%mod*y)%mod)*y%mod ,z=((y*y)%mod*y)%mod*len%mod;
t[cur].sum3=( (a3*t[cur].sum3)%mod+(a2*t[cur].sum2)%mod+(a1*t[cur].sum1)%mod+z )%mod;
a2=(x*x)%mod; a1=((2ll*x)%mod*y)%mod; z=((y*y)%mod*len)%mod;
t[cur].sum2=( (a2*t[cur].sum2)%mod+(a1*t[cur].sum1)%mod+z )%mod;
t[cur].sum1=( x*t[cur].sum1%mod+(y*len)%mod )%mod;
t[cur].mul=(t[cur].mul*x)%mod;
t[cur].lazy=( t[cur].lazy*x%mod+y )%mod;
}
void pushdown( int cur ) //ok
{
if( t[cur].mul!=1ll || t[cur].lazy )
{
cal( ls,t[cur].mul,t[cur].lazy );
cal( rs,t[cur].mul,t[cur].lazy );
t[cur].mul=1ll;
t[cur].lazy=0;
}
}
void build( int cur ,int l,int r )
{
t[cur].l=l;t[cur].r=r;
t[cur].mul=1ll;
t[cur].lazy=t[cur].sum1=t[cur].sum2=t[cur].sum3=0ll;
if( l == r )
{
t[cur].sum1=val[rk[l]];
t[cur].sum2=t[cur].sum1*t[cur].sum1%mod;
t[cur].sum3=t[cur].sum2*t[cur].sum1%mod;
return;
}
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
pushup( cur );
}
void update( int cur,int L,int R ,ll x,ll y )
{
int l=t[cur].l,r=t[cur].r;
if( L<=l && r<=R )
{
cal(cur,x,y);
return;
}
pushdown( cur );
int mid=(l+r)>>1;
if( L<=mid ) update(ls,L,R,x,y);
if( R>mid ) update(rs,L,R,x,y);
pushup( cur );
}
ll get_Sum( int cur,int L,int R )
{
int l=t[cur].l,r=t[cur].r;
if( L<=l && r<=R ) return t[cur].sum3;
ll ans=0;
pushdown( cur );
int mid=(l+r)>>1;
if( L<=mid ) ans+=get_Sum(ls,L,R);
ans%=mod;
if( R>mid ) ans+=get_Sum(rs,L,R);
ans%=mod;
return ans;
}
//*/ 树链剖分
int fa[maxn],dep[maxn],siz[maxn],top[maxn];
// 父亲 深度 大小 重链的头
int v[maxn],son[maxn],dfn[maxn],w[maxn],tim;
// [结点]权值 [结点]重儿子 时间戳(编号) 结点权值的[dfs序] 计数器
void dfs1( int u,int f ) //找重链
{
fa[u]=f; // 父节点
dep[u]=dep[f]+1; //当前深度
siz[u]=1;
int maxsize=-1;
for( int i=head[u];~i;i=edge[i].next )
{
int v=edge[i].to;
if( v==f ) continue;
dfs1(v,u);
siz[u]+=siz[v];
if( siz[v]>maxsize )
{
maxsize=siz[v];
son[u]=v;
}
}
}
void dfs2( int u,int t )
{
dfn[u]=++tim;
top[u]=t;
w[tim]=v[u];
rk[tim]=u;
if( !son[u] ) return;
dfs2(son[u],t);
for( int i=head[u];~i;i=edge[i].next )
{
int v=edge[i].to;
if( v==fa[u] || v==son[u] ) continue;
dfs2(v,v);
}
}
void mchain( int x,int y,ll mu ,ll ad ) //x-y路径上的点操作 z
{
// z%=mod;
while( top[x]!=top[y] )
{
if( dep[top[x]]<dep[top[y]] ) swap(x,y);
update(1,dfn[top[x]],dfn[x],mu,ad);
x=fa[top[x]];
}
if( dep[x]>dep[y] ) swap(x,y);
update(1,dfn[x],dfn[y],mu,ad);
}
ll query( int x,int y )
{
ll ans=0;
while( top[x]!=top[y] )
{
if( dep[top[x]]<dep[top[y]] ) swap(x,y);
ans+=get_Sum(1,dfn[top[x]],dfn[x]);
ans%=mod;
x=fa[top[x]];
}
if( dep[x]>dep[y] ) swap(x,y);
ans+=get_Sum(1,dfn[x],dfn[y]);
return ans%mod;
}
int main()
{
int t,cas=1;
scanf("%d",&t);
while( t-- )
{
tim=0;
int n;
scanf("%d",&n);
init();
for( int i=1;i<n;i++ )
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
for( int i=1;i<=n;i++ )
{
scanf("%lld",&val[i]);
son[i]=0;
dep[i]=0;
}
int r=1; //树的根节点
dep[1]=1;
dfs1(r,r);
dfs2(r,r);
build(1,1,n);
printf("Case #%d:\n",cas++);
int q;
scanf("%d",&q);
while( q-- )
{
int opt,u,v;
ll va;
scanf("%d%d%d",&opt,&u,&v);
if( opt==4 ) printf("%lld\n",query(u,v) );
else
{
scanf("%lld",&va);
if( opt==1 ) mchain(u,v,0ll,va);
else if( opt==2 ) mchain(u,v,1ll,va);
else mchain(u,v,va,0ll);
}
}
}
return 0;
}
H. Tree Partition
大致题意：n结点的树，请你划分成k个分区，当然就是去掉k-1条边，我们定义分区的值为分区中点权之和.你的得分是k个分区中值最大的。请你划分这棵树使得你的得分最小.
分析:二分答案，然后进行dfs check. %%
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
int t,n,k;
ll f[maxn],w[maxn];
vector<int> g[maxn];
int dfs( int u,int fa,ll mx )
{
vector<ll> p;
int cnt=0; // 表示当前节点向下的分区
for( auto v : g[u] )
{
if( v!=fa )
{
cnt+=dfs(v,u,mx);
p.push_back(f[v]);
}
}
sort(p.begin(),p.end());
f[u]=w[u];
for( auto v:p )
{
if( f[u]+v<=mx ) f[u]+=v;
else cnt++;
}
return cnt;
}
int main()
{
int cas=1;
scanf("%d",&t);
while( t-- )
{
scanf("%d%d",&n,&k);
for( int i=1;i<=n;i++ ) g[i].clear();
for( int i=1;i<n;i++ )
{
int u,v;
scanf("%d%d",&u,&v);
g[u].push_back(v);
g[v].push_back(u);
}
ll l=0,r=0,ans=0;
for( int i=1;i<=n;i++ )
{
scanf("%d",&w[i]);
l=max(l,w[i]);
r+=w[i];
}
while( l<=r )
{
ll mid=(l+r)>>1;
if( dfs(1,0,mid)<k )
{
ans=mid;
r=mid-1;
}
else l=mid+1;
}
printf("Case #%d: %lld\n",cas++,ans);
}
}K. Color Graph
大致题意：一张图,n个点m条边,初始所有边为白边,你可以将白边涂成红边.求最大红边数,并且不存在红边奇环.
分析:一共16个点边最多就是120条,显然是数位dp或者暴力枚举等方法.二分图可以判断奇偶问题.那么我们可以用俄二进制表示点选或者不选,然后暴力枚举每条边判断边的两个端点是否在当前集合和集合外，如果是就将这条边涂成红色,否则不涂，不断更新答案.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=305;
struct edge
{
int x,y;
}e[maxn];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
cin>>t;
int cas=1;
while( t-- )
{
int n,m;
cin>>n>>m;
for( int i=0;i<m;i++ )
{
cin>>e[i].x>>e[i].y;
e[i].x--;
e[i].y--;
}
int ans=0;
for( int i=0;i<(1<<n);i++ )
{
int tmp=0;
for( int j=0;j<m;++j )
{
int t1=i>>e[j].x & 1;
int t2=i>>e[j].y & 1;
if( t1+t2==1 ) tmp++;
}
ans=max(ans,tmp);
}
printf("Case #%d: %d\n",cas++,ans);
}
return 0;
}
京公网安备 11010502036488号