Regionals 2013 :: Asia - Dhaka

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

题目链接：UVALive

开的比赛地址：VJ

A:

Falling Ants

水题。找一个H最大的，相同找H*W*L最大的。输出H*W*L;

/* ***
Author :kuangbin
Created Time :2014/7/5 14:07:59
File Name :E:\2014ACM\区域赛练习\2013\2013Dhaka\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;
int L[110],W[110],H[110];

int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
int n;
while(scanf(“%d”,&n) ==1 && n)
{
for(int i = 0;i < n;i++)
scanf(“%d%d%d”,&L[i],&W[i],&H[i]);
int ans = 0;
for(int i = 1;i < n;i++)
if(H[i] > H[ans] || (H[i] == H[ans] && H[i]*W[i]*L[i] > H[ans]*W[ans]*L[ans]))
ans = i;
printf(“%d\n”,H[ans]*L[ans]*W[ans]);
}
return 0;
}

B:

Game of MJ

比较简单的博弈题。稍微分析下就可以了。 每一位上加1的话，有不同效果，有的是模3为0,1,2的。 不同位上进行分类，得到cnt0,cnt1,cnt2,代码这些位上数字操作模3的效果。 可以发现第一个人有两种方法： 1 1 2 1 2 1 2 1 2 1 2…… 2 2 1 2 1 2 1 2 1 2 1…. 1表示模3为1的，2表示模3为2的。 模3为0的可以插入到中间去。 这样分类讨论下就可以知道结果了。 具体看代码吧。

/* ***
Author :kuangbin
Created Time :2014/7/5 14:45:36
File Name :E:\2014ACM\区域赛练习\2013\2013Dhaka\B.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;
int iCase = 0;
scanf(“%d”,&T);
while(T–)
{
iCase++;
long long cnt0 = 0, cnt1 = 0, cnt2 = 0;
scanf(“%d”,&n);
int L,B;
while(n–)
{
scanf(“%d%d”,&L,&B);
if(L == 1)continue;
if(B%3 == 0)
{
cnt0 += (long long)(L-1)(B-1);
}
else if(B%3 == 1)
{
cnt1 += (long long)(L-1)(B-1);
}
else
{
cnt1 += (long long)((L-1)/2)(B-1);
cnt2 += (long long)(L/2)(B-1);
}
}
//不能操作
if(cnt0 == 0 && cnt1 == 0 && cnt2 == 0)
{
printf(“Case %d: Draw\n”,iCase);
continue;
}
if(cnt1 == 0 && cnt2 == 0 && cnt0 != 0)
{
printf(“Case %d: J\n”,iCase);
continue;
}
bool canwin = false;
bool candraw = false;
//对M进行分析
//第一次选余数为1的
if(cnt1)
{
if(cnt1-1 == cnt2 || cnt1-1 == cnt2+1)
{
candraw = true;
}
else
{
if(cnt1-1 < cnt2)
{
if(cnt0%2 == 0)
canwin = true;
}
else
{
if(cnt0%2 == 1)
canwin = true;
}
}
}
if(cnt2)
{
if(cnt2-1 == cnt1 || cnt2-1 == cnt1+1)
candraw = true;
else
{
if(cnt2-1 < cnt1)
{
if(cnt0%2 == 0)
canwin = true;
}
else
{
if(cnt0%2 == 1)
canwin = true;
}
}
}
if(canwin)printf(“Case %d: M\n”,iCase);
else if(candraw)printf(“Case %d: Draw\n”,iCase);
else printf(“Case %d: J\n”,iCase);
}
return 0;
}

C:

Game of Throne

很好的一道题。 主要是转化建模的过程。 N个点的图。每条边有权值。 需要求一个子图。 1~K个点度数为奇数， K+1~N需要度数为偶数。 求子图的最小权值和。 先floyed 一遍，求出两两之间的最短路径。 这样其实就是一个完全图。 度数为偶数的可以不管。 直接看度数为奇数的。 其实就是需要前K个点两两匹配，求最小权值和。 变成了一般图的最小加权匹配。 套一发模板就可以了。

/* ***
Author :kuangbin
Created Time :2014/7/9 19:18:06
File Name :E:\2014ACM\区域赛练习\2013\2013Dhaka\C2.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;
//一般图的最大加权匹配模板
//注意G的初始化,需要偶数个点，刚好可以形成n/2个匹配
//如果要求最小权匹配，可以取相反数，或者稍加修改就可以了
//点的编号从0开始的
const int MAXN = 110;
const int INF = 0x3f3f3f3f;
int G[MAXN][MAXN];
int cnt_node;//点的个数
int dis[MAXN];
int match[MAXN];
bool vis[MAXN];
int sta[MAXN],top;//堆栈
bool dfs(int u)
{
sta[top++] = u;
if(vis[u])return true;
vis[u] = true;
for(int i = 0;i < cnt_node;i++)
if(i != u && i != match[u] && !vis[i])
{
int t = match[i];
if(dis[t] < dis[u] + G[u][i] - G[i][t])
{
dis[t] = dis[u] + G[u][i] - G[i][t];
if(dfs(t))return true;
}
}
top–;
vis[u] = false;
return false;
}
int P[MAXN];
int get_Match(int N)//返回最大匹配权值
{
cnt_node = N;
for(int i = 0;i < cnt_node;i++)P[i] = i;
for(int i = 0;i < cnt_node;i += 2)
{
match[i] = i+1;
match[i+1] = i;
}
int cnt = 0;
while(1)
{
memset(dis,0,sizeof(dis));
memset(vis,false,sizeof(vis));
top = 0;
bool update = false;
for(int i = 0;i < cnt_node;i++)
if(dfs(P[i]))
{
update = true;
int tmp = match[sta[top-1]];
int j = top-2;
while(sta[j] != sta[top-1])
{
match[tmp] = sta[j];
swap(tmp,match[sta[j]]);
j–;
}
match[tmp] = sta[j];
match[sta[j]] = tmp;
break;
}
if(!update)
{
cnt++;
if(cnt >= 3)break;
random_shuffle(P,P+cnt_node);
}
}
int ans = 0;
for(int i = 0;i < cnt_node;i++)
{
int v = match[i];
if(i < v)ans += G[i][v];
}
return ans;
}
int g[MAXN][MAXN];

int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
int T;
int iCase = 0;
int n,m,K;
scanf(“%d”,&T);
while(T–)
{
iCase++;
scanf(“%d%d%d”,&n,&m,&K);
for(int i = 0;i < n;i++)
for(int j = 0;j < n;j++)
{
if(i == j)g[i][j] = 0;
else g[i][j] = INF;
}
int u,v,w;
while(m–)
{
scanf(“%d%d%d”,&u,&v,&w);
u–;
v–;
g[u][v] = g[v][u] = min(g[u][v],w);
}
if(K&1)
{
printf(“Case %d: Impossible\n”,iCase);
continue;
}
for(int k = 0;k < n;k++)
for(int i = 0;i < n;i++)
for(int j = 0;j < n;j++)
g[i][j] = min(g[i][j],g[i][k]+g[k][j]);
for(int i = 0;i < K;i++)
for(int j = 0;j < K;j++)
G[i][j] = -g[i][j];
printf(“Case %d: %d\n”,iCase,-get_Match(K));
}
return 0;
}

D:

Pattern Locker

水题，不多说，直接乘起来加起来就解决了

/* ***
Author :kuangbin
Created Time :2014/7/9 22:21:58
File Name :E:\2014ACM\区域赛练习\2013\2013Dhaka\D.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 long long MOD = 1e13+7;

int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
int T;
int iCase = 0;
int L,N,M;
scanf(“%d”,&T);
while(T–)
{
iCase++;
scanf(“%d%d%d”,&L,&M,&N);
long long ans = 0;
long long tmp = 1;
for(int i = 1;i <= N;i++)
{
tmp = tmp(LL-i+1)%MOD;
if(i >= M)
ans = (ans+tmp)%MOD;
}
printf(“Case %d: %lld\n”,iCase,ans);
}
return 0;
}

F:

Two Points Revisited

水题。简单构造就可以了，保证垂直。

/* ***
Author :kuangbin
Created Time :2014/7/10 17:54:54
File Name :E:\2014ACM\区域赛练习\2013\2013Dhaka\F.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 x1,y1,x2,y2;
scanf(“%d”,&T);
int iCase = 0;
while(T–)
{
iCase++;
scanf(“%d%d%d%d”,&x1,&y1,&x2,&y2);
printf(“Case %d: %d %d %d %d\n”,iCase,y2,x1,y1,x2);
}
return 0;
}

G:

Watching the Kangaroo

胡乱搞一下就可以了。

/* ***
Author :kuangbin
Created Time :2014/7/10 18:13:29
File Name :E:\2014ACM\区域赛练习\2013\2013Dhaka\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 = 100010;
struct Node
{
int x,index;
}node[MAXN];
bool cmp(Node a,Node b)
{
return a.x < b.x;
}
int M;
vectoravec[MAXN];
vectordvec[MAXN];

void gao(int L,int R,int val)
{
int id,l,r;
id = -1;
l = 0; r = M-1;
while(l <= r)
{
int mid = (l+r)/2;
if(node[mid].x >= L)
{
r = mid-1;
id = mid;
}
else l = mid+1;
}
if(id != -1 && node[id].x <= R)
{
avec[id].push_back(val);
id = -1;
l = 0;r = M-1;
while(l <= r)
{
int mid = (l+r)/2;
if(node[mid].x <= R)
{
l = mid+1;
id = mid;
}
else r = mid-1;
}
if(id != -1)
dvec[id].push_back(val);
}
}
int ans[MAXN];
int L[MAXN],R[MAXN];;
int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
int N,T;
int iCase = 0;
scanf(“%d”,&T);
while(T–)
{
iCase++;
printf(“Case %d:\n”,iCase);
scanf(“%d%d”,&N,&M);
for(int i = 0;i < N;i++)
scanf(“%d%d”,&L[i],&R[i]);
for(int i = 0;i < M;i++)
{
scanf(“%d”,&node[i].x);
node[i].index = i;
}
sort(node,node+M,cmp);
for(int i = 0;i < N;i++)
{
gao(L[i],(L[i]+R[i])/2,L[i]);
gao((L[i]+R[i]+1)/2,R[i],R[i]);
}
multisetmt;
multiset::iterator it;
for(int i = 0;i < M;i++)
{
int sz = avec[i].size();
for(int j = 0;j < sz;j++)
mt.insert(avec[i][j]);
ans[node[i].index] = 0;
if(!mt.empty())
{
it = mt.begin();
ans[node[i].index] = max(ans[node[i].index],node[i].x-(it));
it = mt.end();
it–;
ans[node[i].index] = max(ans[node[i].index],(it)-node[i].x);
}
sz = dvec[i].size();
for(int j = 0;j < sz;j++)
{
it = mt.find(dvec[i][j]);
mt.erase(it);
}
}
for(int i = 0;i < M;i++)
printf(“%d\n”,ans[i]);
for(int i = 0;i < M;i++)
{
avec[i].resize(0);
dvec[i].resize(0);
}
}
return 0;
}

H:

GCD XOR

求gcd(A,B) == A^B 1<=B<=A<=N 的对数 首先需要明白的是 如果A^B = tmp的话，那么A,B的差值是不会超过tmp, 这个从二进制很容易想通。 那么如果A,B的gcd为 i, 也就是A,B都是i的倍数。如果 i == A^B 那么A,B的差值只能是i 所以枚举gcd, 假如为i, 那么去判断 j*i 和 (j-1)*i 是不是符合条件。而且 gcd(j*i,(j-1)*i) 一定是i 的，不要再求了。 很容易进行预处理了。

/* ***
Author :kuangbin
Created Time :2014/7/10 18:55:32
File Name :E:\2014ACM\区域赛练习\2013\2013Dhaka\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;
const int MAXN = 30000000;
int f[MAXN+10];
void init()
{
memset(f,0,sizeof(f));
for(int i = 1;i <= MAXN;i++)
{
for(int j = i+i;j <= MAXN;j+=i)
if( (j^(j-i)) == i )
f[j]++;
}
for(int i = 1;i <= MAXN;i++)
f[i] += f[i-1];
}

int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
int T;
int n;
int iCase = 0;
scanf(“%d”,&T);
init();
while(T–)
{
iCase++;
scanf(“%d”,&n);
printf(“Case %d: %d\n”,iCase,f[n]);
}
return 0;
}

I：

Fiasco

按照bfs顺序从小到大去分配边。

/* ***
Author :kuangbin
Created Time :2014/7/13 17:00:43
File Name :E:\2014ACM\区域赛练习\2013\2013Dhaka\I.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 = 2510;
const int MAXM = 50010;
struct Edge
{
int to,next;
int index;
}edge[MAXM];
int head[MAXN],tot;
void init()
{
tot = 0;
memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int index)
{
edge[tot].to = v;
edge[tot].next = head[u];
edge[tot].index = index;
head[u] = tot++;
}

int ST[MAXM],ED[MAXM],W[MAXM];
int ans[MAXM];
bool used[MAXN];

int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
int T;
scanf(“%d”,&T);
int n,m,start;
int iCase = 0;
while(T–)
{
iCase++;
printf(“Case %d:\n”,iCase);
init();
scanf(“%d%d%d”,&n,&m,&start);
for(int i = 0;i < m;i++)
{
scanf(“%d%d%d”,&ST[i],&ED[i],&W[i]);
addedge(ST[i],ED[i],i);
addedge(ED[i],ST[i],i);
}
sort(W,W+m);
queueq;
q.push(start);
memset(used,false,sizeof(used));
memset(ans,-1,sizeof(ans));
used[start] = true;
int id = 0;
while(!q.empty())
{
int u = q.front();
q.pop();
for(int i = head[u];i != -1;i = edge[i].next)
{
int v = edge[i].to;
if(used[v])continue;
used[v] = true;
q.push(v);
ans[edge[i].index] = W[id++];
}
}
for(int i = 0;i < m;i++)
if(ans[i] == -1)
ans[i] = W[id++];
for(int i = 0;i < m;i++)
printf(“%d %d %d\n”,ST[i],ED[i],ans[i]);
}
return 0;
}

J:

Dromicpalin Substrings

直接暴力，统计出现次数。

/* ***
Author :kuangbin
Created Time :2014/7/13 19:54:49
File Name :E:\2014ACM\区域赛练习\2013\2013Dhaka\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;
char str[1010];
int cnt[26];

int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
int T;
int iCase = 0;
scanf(“%d”,&T);
while(T–)
{
iCase++;
scanf(“%s”,str);
int n = strlen(str);
int ans = 0;
for(int i = 0;i < n;i++)
{
memset(cnt,0,sizeof(cnt));
int odd = 0, even = 26;
for(int j = i;j < n;j++)
{
if(cnt[str[j]-‘a’]&1)
{
odd–;
even++;
}
else
{
odd++;
even–;
}
cnt[str[j]-‘a’]++;
if(odd <= 1)ans++;
}
}
printf(“Case %d: %d\n”,iCase,ans);
}
return 0;
}

K:

Fill the Cuboid

直接就是DLX的题目。 直接爆搞会T。 但是要把1*1*1的立方体排除掉。然后数量就不多了。

#include <stdio.h>

#include

#include

#include

#include

#include <string.h>

#include

#include

#include

#include <math.h>
using namespace std;

const int MaxN = 150300;
const int MaxM = 200;
const int maxnode = MaxNMaxM + 10000;
bool used[200];
int CubeSize[MaxN];
struct DLX
{
int n,m,size;
int U[maxnode],D[maxnode],R[maxnode],L[maxnode],Row[maxnode],Col[maxnode];
int H[MaxN],S[MaxM];
void init(int _n,int _m)
{
n = _n;
m = _m;
for(int i = 0;i <= m;i++)
{
S[i] = 0;
U[i] = D[i] = i;
L[i] = i-1;
R[i] = i+1;
}
R[m] = 0; L[0] = m;
size = m;
for(int i = 1;i <= n;i++)H[i] = -1;
}
void Link(int r,int c)
{
++S[Col[++size]=c];
Row[size] = r;
D[size] = D[c];
U[D[c]] = size;
U[size] = c;
D[c] = size;
if(H[r] < 0)H[r] = L[size] = R[size] = size;
else
{
R[size] = R[H[r]];
L[R[H[r]]] = size;
L[size] = H[r];
R[H[r]] = size;
}
}
void remove(int c)
{
L[R[c]] = L[c]; R[L[c]] = R[c];
for(int i = D[c];i != c;i = D[i])
for(int j = R[i];j != i;j = R[j])
{
U[D[j]] = U[j];
D[U[j]] = D[j];
–S[Col[j]];
}
}
void resume(int c)
{
for(int i = U[c];i != c;i = U[i])
for(int j = L[i];j != i;j = L[j])
++S[Col[U[D[j]]=D[U[j]]=j]];
L[R[c]] = R[L[c]] = c;
}
void Dance(int d,int sum)
{
used[d+sum] = true;
if(R[0] == 0)
{
return ;
}
int c = R[0];
for(int i = R[0];i != 0;i = R[i])
{
if(S[i] > S[c])
c = i;
}
remove(c);
for(int i = D[c];i != c;i = D[i])
{
if(CubeSize[Row[i]] == 1)continue;
for(int j = R[i];j != i;j = R[j])remove(Col[j]);
Dance(d+1,sum-CubeSize[Row[i]]);
for(int j = L[i];j != i;j = L[j])resume(Col[j]);
}
resume(c);
}
};
DLX dlx;

bool g[22][22][22];
int id[22][22][22];
vectorvec[MaxN];

int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
int a,b,c,m;
int iCase = 0;
while(scanf(“%d%d%d%d”,&a,&b,&c,&m) == 4)
{
if(a == 0 && b == 0 && c == 0 && m == 0)break;
iCase++;
memset(g,0,sizeof(g));
int x,y,z;
while(m–)
{
scanf(“%d%d%d”,&x,&y,&z);
g[x][y][z] = true;
}
int m = 0;
for(int i = 1;i <= a;i++)
for(int j = 1;j <= b;j++)
for(int k = 1;k <= c;k++)
if(!g[i][j][k])
{
m++;
id[i][j][k] = m;
}
int n = 0;
for(int i = 1;i <= a;i++)
for(int j = 1;j <= b;j++)
for(int k = 1;k <= c;k++)
if(!g[i][j][k])
{
for(int d = 1;;d++)
{
if(i+d-1 > a || j+d-1 > b || k+d-1 > c)break;
bool flag = true;
for(int u = i;u <= i+d-1;u++)
for(int v = j;v <= j+d-1;v++)
for(int w = k;w <= k+d-1;w++)
{
if(g[u][v][w])
{
flag = false;
break;
}
}
if(!flag)break;
n++;
CubeSize[n] = d*d*d;
for(int u = i;u <= i+d-1;u++)
for(int v = j;v <= j+d-1;v++)
for(int w = k;w <= k+d-1;w++)
vec[n].push_back(id[u][v][w]);

                    }
                }
    dlx.init(n,m);
    for(int i = 1;i <= n;i++)
    {
        int sz = vec\[i\].size();
        for(int j = 0 ;j < sz;j++)
            dlx.Link(i,vec\[i\]\[j\]);
    }
    memset(used,false,sizeof(used));
    dlx.Dance(0,m);
    printf("Case %d:",iCase);
    for(int i = 0;i < 200;i++)
        if(used\[i\])
            printf(" %d",i);
    printf("\\n");
    for(int i = 1;i <= n;i++)
        vec\[i\].resize(0);
}
return 0;

}

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