Regionals 2012 :: Europe - Central

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

题目链接：UVALive

VJ比赛地址： here 总体来说，还是有几道好题的。 A：

Kingdoms

题目就是给出了n个人之间的欠款。 每次可以把负债的人删除，问最后只留下一个人，有多少种。 进行DP转移，状态压缩DP。

/* ***
Author :kuangbin
Created Time :2014/6/29 21:18:34
File Name :E:\2014ACM\区域赛练习\2012\2012CERC\A.cpp
************************************************ */

#include <stdio.h>

#include <string.h>

#include

#include

#include

#include

#include

#include

#include

#include <math.h>

#include <stdlib.h>

#include <time.h>
using namespace std;

bool dp[(1<<20)+20];
int two[22];
int a[22][22];
int s[22][(1<<20)+20];
int loc[(1<<22)];

int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
int T;
int n;
scanf(“%d”,&T);
two[0] = 1;
for(int i = 1;i < 22;i++)
{
two[i] = 2*two[i-1];
loc[two[i]] = i;
}
while(T–)
{
scanf(“%d”,&n);
for(int i = 0;i < n;i++)
for(int j = 0;j < n;j++)
scanf(“%d”,&a[i][j]);
for(int i = 0;i < n;i++)
{
s[i][0] = 0;
for(int j = 0;j < n;j++)
s[i][0] += a[i][j];
}
for(int i = 0;i < n;i++)
for(int j = 1;j < two[n];j++)
s[i][j] = s[i][j&(j-1)] - a[i][loc[j&(-j)]];
memset(dp,false,sizeof(dp));
dp[0] = true;
for(int i = 0;i < two[n];i++)
if(dp[i])
{
for(int j = 0;j < n;j++)
if((i&two[j]) == 0 && s[j][i] > 0)
dp[i^two[j]] = true;
}
vectorans;
for(int i = 0;i < n;i++)
if(dp[(two[n]-1)^two[i]])
ans.push_back(i);
if(ans.size() == 0)printf(“0\n”);
else
{
sort(ans.begin(),ans.end());
int sz = ans.size();
for(int i = 0;i < sz;i++)
{
printf(“%d”,ans[i]+1);
if(i < sz-1)printf(“ “);
else printf(“\n”);
}
}
}
return 0;
}

B:

Who wants to live forever?

给出一个01的字符串，每次用s[i-1] xor s[i+1] 去更新s[i], 问最后能不能变成全0 规律题。 C:

Chemist’s vows

纯暴力，打那个表太费劲了。

/* ***
Author :kuangbin
Created Time :2014/6/29 21:53:44
File Name :E:\2014ACM\区域赛练习\2012\2012CERC\C.cpp
************************************************ */

#include <stdio.h>

#include <string.h>

#include

#include

#include

#include

#include

#include

#include

#include <math.h>

#include <stdlib.h>

#include <time.h>
using namespace std;
char str[114][10] =
{
“h” ,”he”,”li”,”be”,”b” ,”c” ,”n” ,”o” ,”f” ,”ne”,
“na”,”mg”,”al”,”si”,”p” ,”s” ,”cl”,”ar”,”k” ,”ca”,
“sc”,”ti”,”v” ,”cr”,”mn”,”fe”,”co”,”ni”,”cu”,”zn”,
“ga”,”ge”,”as”,”se”,”br”,”kr”,”rb”,”sr”,”y” ,”zr”,
“nb”,”mo”,”tc”,”ru”,”rh”,”pd”,”ag”,”cd”,”in”,”sn”,
“sb”,”te”,”i” ,”xe”,”cs”,”ba”,”hf”,”ta”,”w” ,”re”,
“os”,”ir”,”pt”,”au”,”hg”,”tl”,”pb”,”bi”,”po”,”at”,
“rn”,”fr”,”ra”,”rf”,”db”,”sg”,”bh”,”hs”,”mt”,”ds”,
“rg”,”cn”,”fl”,”lv”,
“la”,”ce”,”pr”,”nd”,”pm”,”sm”,”eu”,”gd”,”tb”,”dy”,”ho”,”er”,”tm”,”yb”,”lu”,
“ac”,”th”,”pa”,”u” ,”np”,”pu”,”am”,”cm”,”bk”,”cf”,”es”,”fm”,”md”,”no”,”lr”
};
bool f[50010];

char s[50010];

int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
int T;
scanf(“%d”,&T);
while(T–)
{
scanf(“%s”,s);
memset(f,0,sizeof(s));
int n = strlen(s);
f[0] = true;
for(int i = 1;i <= n;i++)
{
for(int j = 0;j < 114;j++)
{
int len = strlen(str[j]);
if(len == 1 && s[i-1] == str[j][0])
f[i] |= f[i-1];
if(len == 2 && i >= 2 && s[i-1] == str[j][1] && s[i-2] == str[j][0])
f[i] |= f[i-2];
}
}
if(f[n])printf(“YES\n”);
else printf(“NO\n”);
}
return 0;
}

D：

Non-boring sequences

要求任意一个连续子序列都要有一个唯一的元素。 一种做法是分治。 判断一个区间的时候，找出这个区间里面唯一元素，然后分治。 但是为了防止退化，找唯一元素应该从两端找起。就是一前一后找。 如果按照顺序找，是有可能退化的。 代码：

/* ***
Author :kuangbin
Created Time :2014/6/29 22:20:39
File Name :E:\2014ACM\区域赛练习\2012\2012CERC\D1.cpp
************************************************ */

#include <stdio.h>

#include <string.h>

#include

#include

#include

#include

#include

#include

#include

#include <math.h>

#include <stdlib.h>

#include <time.h>
using namespace std;
const int MAXN = 200010;
int a[MAXN];
int L[MAXN];
int R[MAXN];
bool check(int l,int r)
{
if(r <= l)return true;
int index = -1;
for(int i = 0;i < (r-l+1);i++)
{
int id = i&1? l+i/2:r-i/2;
if(L[id] < l && R[id] > r)
{
index = id;
break;
}
}
if(index == -1)return false;
return check(l,index-1) && check(index+1,r);
}

int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
int T;
int n;
scanf(“%d”,&T);
while(T–)
{
scanf(“%d”,&n);
for(int i = 1;i <= n;i++)scanf(“%d”,&a[i]);
map<int,int>mp;
for(int i = 1;i <= n;i++)
{
if(mp.find(a[i]) == mp.end())L[i] = 0;
else L[i] = mp[a[i]];
mp[a[i]] = i;
}
mp.clear();
for(int i = n;i >= 1;i–)
{
if(mp.find(a[i]) == mp.end())R[i] = n+1;
else R[i] = mp[a[i]];
mp[a[i]] = i;
}
if(check(1,n))printf(“non-boring\n”);
else printf(“boring\n”);
}
return 0;
}

另外一种做法是用线段树做的。 维护一个区间的最小值，然后更新区间的值。

/* ***
Author :kuangbin
Created Time :2014/6/29 22:32:15
File Name :E:\2014ACM\区域赛练习\2012\2012CERC\D2.cpp
************************************************ */

#include <stdio.h>

#include <string.h>

#include

#include

#include

#include

#include

#include

#include

#include <math.h>

#include <stdlib.h>

#include <time.h>
using namespace std;

const int MAXN = 200010;
struct Node
{
int l,r;
int Min;
int lazy;
}segTree[MAXN*4];
int a[MAXN];
void Update_Min(int i,int val)
{
if(segTree[i].Min < val)
{
segTree[i].Min = val;
segTree[i].lazy = val;
}
}
void push_down(int i)
{
if(segTree[i].l == segTree[i].r)return;
if(segTree[i].lazy != -1)
{
Update_Min(i<<1,segTree[i].lazy);
Update_Min((i<<1)|1,segTree[i].lazy);
segTree[i].lazy = -1;
}
}
void push_up(int i)
{
if(segTree[i].l == segTree[i].r)return;
segTree[i].Min = min(segTree[i<<1].Min,segTree[(i<<1)|1].Min);
}
void build(int i,int l,int r)
{
segTree[i].l = l;
segTree[i].r = r;
segTree[i].lazy = -1;
if(l == r)
{
segTree[i].Min = a[l];
return;
}
int mid = (l+r)/2;
build(i<<1,l,mid);
build((i<<1)|1,mid+1,r);
push_up(i);
}
void update(int i,int l,int r,int val)
{
if(segTree[i].l == l && segTree[i].r == r)
{
Update_Min(i,val);
return;
}
push_down(i);
int mid = (segTree[i].l + segTree[i].r)/2;
if(r <= mid)update(i<<1,l,r,val);
else if(l > mid)update((i<<1)|1,l,r,val);
else
{
update(i<<1,l,mid,val);
update((i<<1)|1,mid+1,r,val);
}
push_up(i);
}
int query(int i,int l,int r)
{
if(segTree[i].l == l && segTree[i].r == r)
return segTree[i].Min;
push_down(i);
int mid = (segTree[i].l + segTree[i].r)/2;
if(r <= mid)return query(i<<1,l,r);
else if(l > mid)return query((i<<1)|1,l,r);
else
{
return min(query(i<<1,l,mid),query((i<<1)|1,mid+1,r));
}
}
int b[MAXN];
int L[MAXN];
int R[MAXN];

int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
int n;
int T;
scanf(“%d”,&T);
while(T–)
{
scanf(“%d”,&n);
for(int i = 1;i <= n;i++)
scanf(“%d”,&b[i]);
map<int,int>mp;
for(int i = 1;i <= n;i++)
{
if(mp.find(b[i]) == mp.end())L[i] = 1;
else L[i] = mp[b[i]]+1;
mp[b[i]] = i;
}
mp.clear();
for(int i = n;i >= 1;i–)
{
if(mp.find(b[i]) == mp.end())R[i] = n;
else R[i] = mp[b[i]]-1;
mp[b[i]] = i;
a[i] = R[i];
}
build(1,1,n);
bool flag = true;
for(int i = 2;i <= n;i++)
{
if(query(1,1,i-1) < i)
{
flag = false;
break;
}
update(1,L[i],i,R[i]);
}
if(flag)printf(“non-boring\n”);
else printf(“boring\n”);
}
return 0;
}

E:

Word equations

DP dp[i][j] 表示第i个点，从j这个位置匹配，匹配到的最远位置。

/* ***
Author :kuangbin
Created Time :2014/7/2 13:06:54
File Name :E:\2014ACM\区域赛练习\2012\2012CERC\E.cpp
************************************************ */

#include <stdio.h>

#include <string.h>

#include

#include

#include

#include

#include

#include

#include

#include <math.h>

#include <stdlib.h>

#include <time.h>
using namespace std;
const int MAXN = 1010;

map<string,int>mp;
vectorvec[MAXN];
char s[MAXN][10];

char str1[20],str2[20],str3[20];
char aim[2020];
int n;
int dp[MAXN][2020];
void solve(int u)
{
if(dp[u][0] != -1)return ;
if(vec[u].size() == 2)
{
solve(vec[u][0]);
solve(vec[u][1]);
for(int i = 0;i <= n;i++)
dp[u][i] = dp[vec[u][1]][dp[vec[u][0]][i]];
}
else
{
int v = vec[u][0];
dp[u][n] = n;
int len = strlen(s[v]);
for(int i = 0;i < n;i++)
{
int id1 = i;
int id2 = 0;
while(id1 < n && id2 < len)
{
while(id2 < len && aim[id1] != s[v][id2])
id2++;
if(id2 < len && aim[id1] == s[v][id2])
{
id1++;
id2++;
}
}
dp[u][i] = id1;
}
}
}

int main()
{
//freopen(“3.in”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
int T;
int k;
scanf(“%d”,&T);
while(T–)
{
scanf(“%d”,&k);
for(int i = 0;i < MAXN;i++)
vec[i].clear();
mp.clear();
int tot = 0;
for(int i = 0;i < k;i++)
{
scanf(“%s = %s”,str1,str2);
if(mp.find(str1) == mp.end())
{
strcpy(s[tot],str1);
mp[str1] = tot++;
}
if(mp.find(str2) == mp.end())
{
strcpy(s[tot],str2);
mp[str2] = tot++;
}
vec[mp[str1]].push_back(mp[str2]);
if(str2[0] >= ‘A’ && str2[0] <= ‘Z’)
{
scanf(“%s%s”,str2,str3);
if(mp.find(str3) == mp.end())
{
strcpy(s[tot],str3);
mp[str3] = tot++;
}
vec[mp[str1]].push_back(mp[str3]);
}
}
scanf(“%s%s”,str1,aim);
n = strlen(aim);
memset(dp,-1,sizeof(dp));
solve(mp[str1]);
if(dp[mp[str1]][0] == n)
printf(“YES\n”);
else printf(“NO\n”);
}
return 0;
}

G:

Jewel heist

从低到高扫描。 各类点分别处理，找出一个个小矩形。

/* ***
Author :kuangbin
Created Time :2014/7/2 21:32:41
File Name :E:\2014ACM\区域赛练习\2012\2012CERC\G.cpp
************************************************ */

#include <stdio.h>

#include <string.h>

#include

#include

#include

#include

#include

#include

#include

#include <math.h>

#include <stdlib.h>

#include <time.h>
using namespace std;

const int MAXN = 200010;
struct BIT
{
int c[MAXN];
int n;
int lowbit(int x)
{
return x&(-x);
}
void init(int _n)
{
n = _n;
memset(c,0,sizeof(c));
}
void add(int i,int val)
{
while(i <= n)
{
c[i] += val;
i += lowbit(i);
}
}
int sum(int i)
{
int s = 0;
while(i > 0)
{
s += c[i];
i -= lowbit(i);
}
return s;
}
int sum(int l,int r)
{
if(l > r)return 0;
return sum(r) - sum(l-1);
}
}bt;
struct Point
{
int x,y;
int c;
}p[MAXN];
bool cmp(Point p1,Point p2)
{
return p1.y < p2.y;
}
int sx[MAXN];

setst[MAXN];

int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
int T;
int n,k;
scanf(“%d”,&T);
while(T–)
{
scanf(“%d%d”,&n,&k);
int tot = 0;
for(int i = 0;i < n;i++)
{
scanf(“%d%d%d”,&p[i].x,&p[i].y,&p[i].c);
sx[tot++] = p[i].x;
}
sort(sx,sx+tot);
tot = unique(sx,sx+tot) - sx;
bt.init(tot);
for(int i = 0;i < n;i++)
p[i].x = lower_bound(sx,sx+tot,p[i].x) - sx + 1;
sort(p,p+n,cmp);
for(int i = 1;i <= k;i++)
st[i].clear();
for(int i = 1;i <= k;i++)
{
st[i].insert(0);
st[i].insert(tot+1);
}
int ans = 0;
set::iterator it;
for(int i = 0;i < n;i++)
{
int ni = i;
for(;ni < n && p[ni].y == p[i].y;ni++)
{
it = st[p[ni].c].lower_bound(p[ni].x);
int end = (it)-1;
it–;
int start = (it)+1;
ans = max(ans,bt.sum(start,end));
}
for(int j = i;j < ni;j++)
{
bt.add(p[j].x,1);
st[p[j].c].insert(p[j].x);
}
i = ni-1;
}
for(int i = 1;i <= k;i++)
{
it = st[i].begin();
it++;
int pre = 0;
while(it != st[i].end())
{
ans = max(ans,bt.sum(pre+1,(it)-1));
pre = it;
it++;
}
}
printf(“%d\n”,ans);
}
return 0;
}

H:

Darts

水题，不解释。

/* ***
Author :kuangbin
Created Time :2014/7/2 19:48:35
File Name :E:\2014ACM\区域赛练习\2012\2012CERC\CERC2012\e\H.cpp
************************************************ */

#include <stdio.h>

#include <string.h>

#include

#include

#include

#include

#include

#include

#include

#include <math.h>

#include <stdlib.h>

#include <time.h>
using namespace std;

int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
int T;
int n;
scanf(“%d”,&T);
while(T–)
{
scanf(“%d”,&n);
int ans = 0;
int x,y;
while(n–)
{
scanf(“%d%d”,&x,&y);
for(int i = 10;i >= 1;i–)
if(x*x + y*y <= 20(11-i)\20*(11-i))
{
ans += i;
break;
}
}
printf(“%d\n”,ans);
}
return 0;
}

I：

The Dragon and the knights

N条直线，把平面分成了若干部分，需要判断是不是每个区域都有人。 首先使用公式求出分成的区域。 然后使用了set去判断，就是点在直线的哪一侧，就可以知道在哪个区域了。

#include <stdio.h>

#include

#include

#include

#include

#include <string.h>

#include

#include

#include

#include <math.h>
using namespace std;

int A[110],B[110],C[110];
int X[50010],Y[50010];

bool check(int i,int j)
{
long long tmp = (long long)A[i]*B[j] - (long long)B[i]*A[j];
if(tmp == 0)return false;
return true;
}

set<pair >st;
int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
int n,m;
int T;
scanf(“%d”,&T);
while(T–)
{
scanf(“%d%d”,&n,&m);
for(int i = 0;i < n;i++)scanf(“%d%d%d”,&A[i],&B[i],&C[i]);
for(int i = 0;i < m;i++)scanf(“%d%d”,&X[i],&Y[i]);
int E = 0;
int V = 0;
for(int i = 0;i < n;i++)
{
int cnt = 0;
for(int j = 0;j < n;j++)
if(i != j)
if(check(i,j))
cnt++;
E += cnt+1;
V += cnt;
}
V /= 2;
int tot = 1+E - V;
st.clear();
for(int i = 0;i < m;i++)
{
long long tmp1 = 0;
long long tmp2 = 0;
for(int j = 0;j < n;j++)
{
long long tmp = (long long)A[j]*X[i] + (long long)B[j]*Y[i] + C[j];
if(tmp > 0)
{
if(j < 50)
tmp1 |= (1LL << j);
else tmp2 |= (1LL << (j-50));
}
}
st.insert(make_pair(tmp1,tmp2));
}
if(st.size() == tot)printf(“PROTECTED\n”);
else printf(“VULNERABLE\n”);
}
return 0;
}

J：

Conservation

使用两个队列进行拓扑排序。 本题数据组数很多，如果用memset初始化会慢非常多。

/* ***
Author :kuangbin
Created Time :2014/7/2 20:12:02
File Name :E:\2014ACM\区域赛练习\2012\2012CERC\J.cpp
************************************************ */

#include <stdio.h>

#include <string.h>

#include

#include

#include

#include

#include

#include

#include

#include <math.h>

#include <stdlib.h>

#include <time.h>
using namespace std;
const int MAXN = 100010;
const int MAXM = 1000010;
const int INF = 0x3f3f3f3f;
struct Edge
{
int to,next;
}edge[MAXM];
int head[MAXN],tot;
void init()
{
tot = 0;
//memset(head,-1,sizeof(head));
}
void addedge(int u,int v)
{
edge[tot].to = v;
edge[tot].next = head[u];
head[u] = tot++;
}
int a[MAXN];
int in[MAXN];
int tmpin[MAXN];
int solve(int s,int n)
{
for(int i = 1;i <= n;i++)
in[i] = tmpin[i];
queueq[2];
for(int i = 1;i <= n;i++)
if(in[i] == 0)
q[a[i]].push(i);
int now = s;
int ans = 0;
int cnt = 0;
while(1)
{
if(q[now].empty())break;
ans++;
while(!q[now].empty())
{
int u = q[now].front();
q[now].pop();
cnt++;
for(int i = head[u];i != -1;i = edge[i].next)
{
int v = edge[i].to;
in[v]–;
if(in[v] == 0)
q[a[v]].push(v);
}
}
now ^= 1;
}
if(cnt != n)return INF;
return ans-1;
}

int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
int T;
int n,m;
int u,v;
scanf(“%d”,&T);
while(T–)
{
scanf(“%d%d”,&n,&m);
for(int i = 1;i <= n;i++)
{
scanf(“%d”,&a[i]);
a[i]–;
}
init();
for(int i = 1;i <= n;i++)
{
head[i] = -1;
in[i] = 0;
}
//memset(in,0,sizeof(in));
while(m–)
{
scanf(“%d%d”,&u,&v);
addedge(u,v);
in[v]++;
}
for(int i = 1;i <= n;i++)tmpin[i] = in[i];
printf(“%d\n”,min(solve(0,n),solve(1,n)));
}
return 0;
}

------ 本文结束------
  • 本文作者： kuangbin
  • 本文链接： 199.html
  • 版权声明： 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处！
0%