The 36th ACM/ICPC Asia Regional Dalian Online Contest 大连2011ICPC网络赛 个人题解

好久不写题,外加上在准备考研,这次有点悲剧,比赛时A了5题,还有一题有点小BUG,比赛后才A。。今年要考南京大学~也没时间准备ICPC了,希望我们队里的那个小孩子能够快快成长起来,我这个队长也可以安心的卸任了,明年将最后一次比赛机会放在NJU吧~恩,顺便去看下高中膜拜过的蒋炎研同学~江苏大学加油!
第一题:
其实就是构建一个DAG,然后再DAG上求最长路径。要注意构图时候避免环,特别考虑当两个木块长宽都一致而且都是d=0类型的时候。对了,还有一个阴险的地方,长宽可以互换的~复杂度O(n2)
 1# include <cstdio>
 2# include <cstring>
 3# include <algorithm>
 4using namespace std;
 5int n;
 6# define N 1005
 7# define M 1000005
 8int data[N][4];
 9int g[N],nxt[M],v[M],val[M],c;
10long long len[N];
11long long dp(int pos)
12{
13    if(len[pos]!=-1return len[pos];
14    else
15    {
16        len[pos]=0;
17        for(int p=g[pos];p!=-1;p=nxt[p])
18            len[pos]=max(len[pos],dp(v[p])+val[p]);
19        return len[pos];
20    }

21}

22void insert(int s,int e,int value)
23{
24    v[c]=e;
25    val[c]=value;
26    nxt[c]=g[s];
27    g[s]=c++;
28}

29int main()
30{
31    while(scanf("%d",&n)&&n)
32    {
33        for(int i=0;i<n;i++)
34        {
35            scanf("%d%d%d%d",&data[i][0],&data[i][1],&data[i][2],&data[i][3]);
36            if(data[i][0]>data[i][1]) swap(data[i][0],data[i][1]);
37        }

38        memset(g,-1,sizeof(g));
39        memset(len,-1,sizeof(len));
40        c=0;
41        for(int i=0;i<n;i++)
42            for(int j=0;j<n;j++)
43                switch(data[i][3])
44                {
45                case 0:
46                    if(data[j][0]<=data[i][0]&&data[j][1]<=data[i][1]&&!(data[j][0]==data[i][0]&&data[j][1]==data[i][1]&&data[j][3]==data[i][3]&&j>=i))
47                        insert(i,j,data[j][2]);
48                    break;
49                case 1:
50                    if(data[j][0]<=data[i][0]&&data[j][1]<=data[i][1]&&((long long)data[j][0]*data[j][1])<((long long)data[i][0]*data[i][1]))
51                        insert(i,j,data[j][2]);
52                    break;
53                case 2:
54                    if(data[j][0]<data[i][0]&&data[j][1]<data[i][1])
55                        insert(i,j,data[j][2]);
56                    break;
57                }
;
58        for(int i=0;i<n;i++)
59            insert(n,i,data[i][2]);
60        printf("%I64d\n",dp(n));
61    }

62    return 0;
63}


第二题:一个数论题目,当时没有证明,直接找规律的,具体的就是质数连成。恩。代码是队里的大一的孩子写的,就直接贴了。复杂度打好表的画就是个二分查找的复杂度
1#include<cstdio>
2#include<cmath>
3#include<cstdlib>
4#include<cstring>
5
6using namespace std;
7
8const int tablesize=64;
9const int primesize=2000;
10bool isprime[primesize+1];
11int pt[primesize];
12int mytable[tablesize+1][150];
13inline void multiple(int* a,int b);
14void getprime(int n);
15void getmytable(int tablesize);
16void getdata_and_solve();
17void find_the_ans(char* ts);
18void zhuanhuan(int* a,char* ts);
19int dayu(int* a,int* b);
20
21int main()
22{
23 getprime(primesize);
24 getmytable(tablesize);
25 getdata_and_solve();
26 return 0;
27}

28
29inline void multiple(int* a,int b)
30{
31 int len=a[0];
32 int i;
33 a[1]*=b;
34 for (i=2;i<=len;++i)
35 {
36 a[i]=a[i]*b+a[i-1]/10;
37 a[i-1]%=10;
38 }

39 while (a[len]>9) {++len; a[len]=a[len-1]/10; a[len-1]%=10;}
40 a[0]=len;
41}

42
43void getprime(int n)
44{
45 int i;
46 for (i=1;i<=n;++i) isprime[i]=true;
47 isprime[1]=false;
48 int j;
49 i=1;
50 while (++i<=n)
51 if (isprime[i])
52 {
53 j=i;
54 while ((j+=i)<=n)
55 isprime[j]=false;
56 }

57 pt[0]=0;
58 for (i=1;i<=n;++i)
59 if (isprime[i]) pt[++pt[0]]=i;
60}

61
62void getmytable(int tablesize)
63{
64 int j,i,len;
65 mytable[1][0]=1; mytable[1][1]=2;
66 for (i=2;i<=tablesize;++i)
67 {
68 len=mytable[i-1][0];
69 for (j=0;j<=len;++j)
70 mytable[i][j]=mytable[i-1][j];
71 multiple(mytable[i],pt[i]);
72 }

73}

74
75void getdata_and_solve()
76{
77 char ts[200];
78 int n;
79 scanf("%d",&n);
80 getchar();
81 int i;
82 for (i=1;i<=n;++i)
83 {
84 gets(ts);
85 find_the_ans(ts);
86 }

87}

88
89void find_the_ans(char* ts)
90{
91 int l=1,r=tablesize;
92 int mid;
93 int shuju[150];
94 zhuanhuan(shuju,ts);
95 int lena,lenb=shuju[0];
96 int flag;
97 int i;
98 while (l+1<r)
99 {
100 mid=((l+r)>>1);
101 lena=mytable[mid][0];
102 if (lena>lenb) flag=1; //a>b;
103 else
104 if (lena<lenb) flag=-1; //a<b;
105 else
106 {
107 flag=0;
108 for (i=lena;i>=1;--i)
109 {
110 if (mytable[mid][i]>shuju[i]) {flag=1; break;}
111 else if (mytable[mid][i]<shuju[i]) {flag=-1; break;}
112 }

113 }

114
115 if (flag==0) {l=mid; break;}
116 else if(flag==1) r=mid;
117 else l=mid;
118 }

119
120 for (i=mytable[l][0];i>=1;--i) printf("%d",mytable[l][i]);
121 putchar('\n');
122}

123
124 void zhuanhuan(int* a,char* ts)
125{
126 int len=strlen(ts);
127 int i;
128 for (i=0;i<len;++i)
129 a[len-i]=ts[i]-'0';
130 a[0]=len;
131}

132

1003 是个TREE-DP,好久不动了,不敢写。。等会来实现下
1004 一个二分+验证的问题。先二分最长长度,然后用BFS验证。其实都不用BFS,因为是个严格单调的序列,直接DFS更简单
1# include <cstdio>
2# include <algorithm>
3# include <queue>
4using namespace std;
5int n,m,l;
6# define N 500005
7int d[N],dis[N];
8queue<int> q;
9bool chk(int len)
10{
11 if(len>=l) return true;
12 while(!q.empty()) q.pop();
13 int pos=upper_bound(d,d+n,len)-d-1;
14 if(pos<0) return false;
15 dis[pos]=1;
16 if(m<=dis[pos]) return false;
17 q.push(pos);
18 while(!q.empty())
19 {
20 int top=q.front();
21 q.pop();
22 if(d[top]+len>=l) return true;
23 pos=upper_bound(d,d+n,d[top]+len)-d-1;
24 if(pos<0||d[pos]<=d[top]||dis[top]+1>=m) return false;
25 dis[pos]=dis[top]+1;
26 q.push(pos);
27 }

28 return false;
29}

30int main()
31{
32 while(scanf("%d%d%d",&l,&n,&m)!=EOF)
33 {
34 for(int i=0;i<n;i++)
35 scanf("%d",d+i);
36 sort(d,d+n);
37 int s=0,e=l;
38 while(s<=e)
39 {
40 int mid=(s+e)/2;
41 if(chk(mid)) e=mid-1;
42 else s=mid+1;
43 }

44 printf("%d\n",e+1);
45 }

46 return 0;
47}

1005 木有思想
1006这题NC了,当时想都没想直接手写树状数组+二分,现在想想看这题条件太特殊了,询问的位置是一定的,就是一个简单的最小堆= =。。。不过还是把树状数组的NC版本代码贴出来吧。。
Title
1# include <cstdio>
2# include <cstring>
3# include <vector>
4# include <utility>
5# include <functional>
6# include <algorithm>
7using namespace std;
8# define N 1000005
9int arr[N],maxnum;
10# define lowbit(num) ((num)&-(num))
11pair<bool,int> q[N];
12vector<int> list;
13void add(int val)
14{
15 for(;val<=maxnum;val+=lowbit(val))
16 arr[val]++;
17}

18int sum(int pos)
19{
20 int res=0;
21 for(;pos>0;pos-=lowbit(pos))
22 res+=arr[pos];
23 return res;
24}

25int search(int m)
26{
27 int s=1,e=maxnum,total=sum(maxnum);
28 while(s<=e)
29 {
30 int mid=(s+e)/2;
31 if(total-sum(mid-1)>=m) s=mid+1;
32 else e=mid-1;
33 }

34 return s-1;
35}

36int main()
37{
38 int n,m;
39 while(scanf("%d%d",&n,&m)!=EOF)
40 {
41 list.clear();
42 memset(arr,0,sizeof(arr));
43 for(int i=0;i<n;i++)
44 {
45 char type[5];
46 scanf("%s",type);
47 if(type[0]=='I')
48 {
49 q[i].first=true;
50 scanf("%d",&q[i].second);
51 list.push_back(q[i].second);
52 }

53 else q[i].first=false;
54 }

55 sort(list.begin(),list.end());
56 maxnum=list.size();
57 for(int i=0;i<n;i++)
58 {
59 if(q[i].first)
60 add(lower_bound(list.begin(),list.end(),q[i].second)-list.begin()+1);
61 else
62 printf("%d\n",list[search(m)-1]);
63 }

64 }

65 return 0;
66}

1007 一个经典的动态统计,我写这类题目时都会很偷懒的用STL的set,呵呵~
Title
1# include <cstdio>
2# include <algorithm>
3# include <utility>
4# include <functional>
5# include <map>
6using namespace std;
7int n,r;
8# define N 1005
9pair<int,int> data[N];
10map<int,int> refer;
11bool cmpy(const pair<int,int> &a,const pair<int,int> &b)
12{
13 return a.second<b.second;
14}

15void cal(int &maxnum)
16{
17 if(refer.empty()) return;
18 int total=0;
19 map<int,int>::iterator last=refer.begin();
20 for(map<int,int>::iterator i=refer.begin();i!=refer.end();i++)
21 {
22 while(i->first-last->first>r)
23 total-=last->second,last++;
24 total+=i->second;
25 maxnum=max(maxnum,total);
26 }

27}

28int main()
29{
30 while(scanf("%d%d",&n,&r)!=EOF)
31 {
32 for(int i=0;i<n;i++)
33 scanf("%d%d",&data[i].first,&data[i].second);
34 sort(data,data+n,cmpy);
35 int last=0;
36 refer.clear();
37 int maxnum=0;
38 for(int now=0;now<n;now++)
39 {
40 while(data[now].second-data[last].second>r)
41 {
42 refer[data[last].first]--;
43 if(refer[data[last].first]==0) refer.erase(data[last].first);
44 last++;
45 }

46 refer[data[now].first]++;
47 cal(maxnum);
48 }

49 printf("%d\n",maxnum);
50 }

51 return 0;
52}

53
1008 比赛时间来不及了,当时,以为写出5题,能够稳了,yzu的同学来了个电话,说这次比赛5题已经排到150了。。大惊。。连忙回去看题。。但是。。哎。。
不扯淡了,写写这题思想。看复杂度,非O(n)的算法不行的说
差不多定下来是TREE-DP
首先构造以1为根的树
然后主要解决3个问题
1、判断询问时X节点是再Y节点的子孙节点还是其祖先节点(相对于以1为根的树)
2、分别讨论以上两种情况下的解
第一问我是这样解决的
首先记录下以1为根的树的dfn(DFS遍历序列),如果X是Y的子孙节点当且仅当dfn(x)>=dfn(y)且dfn(x)<=max(dfn(z)),z是y的子孙节点。这里要tree-dp处理max(dfn(z))。
第二问的解决就很销魂了
首先,如果X是Y的祖先节点,那么问题就转化为求以Y为根的子树的问题,可以直接利用以1为根的树的DP出来的结果。(即以K为根的子树儿子编号的最小值以及子孙编号的最小值以及次小值(这个后面会说有什么用),这个TREE-DP大家肯定都会的)
X是Y的儿子节点
这个麻烦一点,首先利用DFN可以很快的确定根在Y的哪棵子树上,如果最小值取在这棵子树上,那么取Y的次小值,否则就取最小值。然后如果Y节点不是1号节点的话,其最小儿子(相对于以Y为根的子树)编号再与其父亲(相对于以1为根的子树)取个最小值,最小子孙(相对于以Y为根的子树)编号与1取最小值。
然后上代码~
 1# include <cstdio>
 2# include <vector>
 3# include <algorithm>
 4# define max(a,b) ((a)>(b)?(a):(b))
 5using namespace std;
 6# define N 100005
 7vector<int>    g[N];
 8int dfn[N],c=0,maxdfn[N];
 9int n,q;
10int dp[N],fa[N];
11int ans[N][5];
12void update(int tmp[],int pos)
13{
14    if(pos<tmp[0]) tmp[1]=tmp[0],tmp[0]=pos;
15    else if(pos<tmp[1]) tmp[1]=pos;
16    if(dp[pos]<tmp[2]) tmp[3]=tmp[2],tmp[2]=dp[pos],tmp[4]=pos;
17    else if(dp[pos]<tmp[3]) tmp[3]=dp[pos];
18}

19void dfs(int pos,int pre)
20{
21    dp[pos]=pos;
22    maxdfn[pos]=dfn[pos]=c++;
23    ans[pos][0]=ans[pos][1]=ans[pos][2]=ans[pos][3]=0xfffffff;
24    for(int i=0;i<g[pos].size();i++)
25    if(g[pos][i]!=pre)
26        {
27            dfs(g[pos][i],pos);
28            if(dp[g[pos][i]]<dp[pos])
29                dp[pos]=dp[g[pos][i]];
30            maxdfn[pos]=max(maxdfn[pos],maxdfn[g[pos][i]]);
31            update(ans[pos],g[pos][i]);
32        }

33    
34    fa[pos]=pre;
35}

36int main()
37{
38    int t;
39    scanf("%d",&t);
40    while(t--)
41    {
42        scanf("%d%d",&n,&q);
43        for(int i=1;i<=n;i++) g[i].clear();
44        for(int i=1;i<n;i++)
45        {
46            int a,b;
47            scanf("%d%d",&a,&b);
48            g[a].push_back(b);
49            g[b].push_back(a);
50        }

51        c=0;
52        dfs(1,1);
53
54        while(q--)
55        {
56            int x,y;
57            scanf("%d%d",&x,&y);
58            if(dfn[x]<dfn[y]||dfn[x]>maxdfn[y])//根在上方
59            {
60                int ans1=ans[y][0],ans2=ans[y][2];
61                if(ans1==0xfffffff) printf("no answers!\n");
62                else printf("%d %d\n",ans1,ans2);
63            }

64            else//根在子树中
65            {
66                int ans1=(dfn[x]>=dfn[ans[y][0]]&&dfn[x]<=maxdfn[ans[y][0]]?ans[y][1]:ans[y][0]),
67                    ans2=(dfn[x]>=dfn[ans[y][4]]&&dfn[x]<=maxdfn[ans[y][4]]?ans[y][3]:ans[y][2]);
68                if(y!=1) ans1=min(ans1,fa[y]),ans2=min(ans2,1);
69                if(ans1==0xfffffff) printf("no answers!\n");
70                else printf("%d %d\n",ans1,ans2);
71            }

72        }

73        printf("\n");
74    }

75    return 0;
76}
1009 当时没来得及看,小朋友太纯真的说费用流,我就无语了。。不过这事都是给了我启发。。不会想到有向图的最小生成树的时候太迟了。。
1010 不知道

最后再次祝福ujs Genius_Cats 在解体前能够有个好成绩~
Genius Cats 队长:yzhw

posted on 2011-09-04 10:42 yzhw 阅读(1815) 评论(6)  编辑 收藏 引用 所属分类: DPgraph

评论

# re: The 36th ACM/ICPC Asia Regional Dalian Online Contest 大连2011ICPC网络赛 个人题解 2011-09-04 19:08 PWK

补上1005题目思路,在这题的思路是对点进行割边的缩点从构图,如果2点2连通,那么他们连通的边是不能破坏的。能破坏的只有割边。由void DFS(int x,int farther) ,void Set_Color(int x)完成。完成后成为一棵树。之后就是博弈问题啦,做完敌人,他们要找到一条链,使得能尽量多的删除最小的边。不能删除的最小边权值则是这题的解。删除最小的边的方法是以最小边的两个点为根,分别构建树,树形DP,求节点下面的哪条路有最小边,找到不走的边的最小权值。输出。
#include <iostream>
#include <vector>
using namespace std;
#define maxn 10005
int MinN(int x,int y) {return x<y?x:y;}
struct node{int v,w;};
vector<node> map[maxn],newmap[maxn];
int DFn[maxn]; //深搜时节点的访问顺序
int low[maxn]; //存放当前接点不经过其父亲节点能够访问DFn值最小的节点
int color[maxn];
int dp[maxn];
int index;
int n,m,q;
int minu,minv,minw;
bool done[maxn];


void DFS(int x,int farther)
{
int i;
DFn[x]=low[x]=index++;//赋初值
for(i=0;i<map[x].size();i++)
{
if(!DFn[map[x][i].v])
{
DFS(map[x][i].v,x);
low[x]=MinN(low[x],low[map[x][i].v]);//检查子节点能返回的最早的祖先
}
else if(farther!=map[x][i].v)
low[x]=MinN(low[x],DFn[map[x][i].v]);//检查从自身出发的后向边(无向图中没有横叉边)
}
}
void Set_Color(int x)//染色,同一双连通分量内的节点用一种颜色
{
int i;
node tmp;
for(i=0;i<map[x].size();i++)
{
if(!color[map[x][i].v])
{
if(low[map[x][i].v]>DFn[x]) //(node,map[node][i])是割边
{
color[map[x][i].v]=index++;
tmp.v=color[map[x][i].v];tmp.w=map[x][i].w;
newmap[color[x]].push_back(tmp);
tmp.v=color[x];
newmap[color[map[x][i].v]].push_back(tmp);
if(map[x][i].w<minw)
{
minw=map[x][i].w;
minu=color[x];
minv=color[map[x][i].v];
}
}
else color[map[x][i].v]=color[x]; //非割边,即说明两个节点处在同以双连通分量中
Set_Color(map[x][i].v);
}
}
}


int DFSDP(int x,int dist)
{
done[x]=1;
dp[x]=dist;
int i,a;
for(i=0;i<newmap[x].size();i++)
{
if(!done[newmap[x][i].v])
{
a=DFSDP(newmap[x][i].v,newmap[x][i].w);
dp[x]=MinN(dp[x],a);
}
}
return dp[x];
}

void dfs(int x)
{
done[x]=1;
int min1=100001,min2=100001,i,v=-1;
for(i=0;i<newmap[x].size();i++)
{
if(!done[newmap[x][i].v])
{
if(dp[newmap[x][i].v]<=min1) {min2=min1;min1=dp[newmap[x][i].v];v=newmap[x][i].v;}
else if(dp[newmap[x][i].v]<=min2) min2=dp[newmap[x][i].v];
}
}
q=MinN(min2,q);
if(v!=-1) DFS(v);
}

int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
int a,b,w,i;
node tmp;
for(i=0;i<maxn;i++)
{
map[i].clear();
newmap[i].clear();
}
for(i=0;i<m;i++)
{
scanf("%d%d%d",&a,&b,&w);
tmp.v=b-1;tmp.w=w;
map[a-1].push_back(tmp);
tmp.v=a-1;
map[b-1].push_back(tmp);
}
index=1;
memset(DFn,0,sizeof(DFn));
DFS(0,-1);
memset(color,0,sizeof(color));
color[0]=1;
index=2;
minw=100001;
Set_Color(0);
memset(dp,-1,sizeof(dp));
memset(done,0,sizeof(done));
done[minu]=done[minv]=1;
DFSDP(minu,minw);
DFSDP(minv,minw);
q=100001;
memset(done,0,sizeof(done));
done[minu]=done[minv]=1;
dfs(minu);
dfs(minv);
if(q!=100001) printf("%d\n",q);
else printf("-1\n");
}
return 0;
}   回复  更多评论   

# re: The 36th ACM/ICPC Asia Regional Dalian Online Contest 大连2011ICPC网络赛 个人题解 2011-09-04 19:13 PWK

代码粘错啦,比赛的时候代码写的太挫啦,发现命名了2个DFS,后面那个改小写啦,粘的中每改。dfs函数中的dfs函数改成小写。
void dfs(int x)
{
done[x]=1;
int min1=100001,min2=100001,i,v=-1;
for(i=0;i<newmap[x].size();i++)
{
if(!done[newmap[x][i].v])
{
if(dp[newmap[x][i].v]<=min1) {min2=min1;min1=dp[newmap[x][i].v];v=newmap[x][i].v;}
else if(dp[newmap[x][i].v]<=min2) min2=dp[newmap[x][i].v];
}
}
q=MinN(min2,q);
if(v!=-1) dfs(v);
}  回复  更多评论   

# re: The 36th ACM/ICPC Asia Regional Dalian Online Contest 大连2011ICPC网络赛 个人题解[未登录] 2011-09-05 08:44 yzhw

@PWK
谢谢你~  回复  更多评论   

# re: The 36th ACM/ICPC Asia Regional Dalian Online Contest 大连2011ICPC网络赛 个人题解 2011-09-05 22:43 waterman

问问博主,对于1008,如果x在y为根的子树上,且最小值在x所在的这棵子树上,就取次小的值,那么如果次小的值也在x所在的这棵子树上,是否要继续考虑第三小的值呢?  回复  更多评论   

# re: The 36th ACM/ICPC Asia Regional Dalian Online Contest 大连2011ICPC网络赛 个人题解 2011-09-06 09:21 yzhw

@waterman
这里的次小值是节点P中儿子子树最小值的次小值,换句话说,假设把所有儿子子树的最小值放在一个列表中,然后排个序的话,该子树节点的次小值是排位第二的元素(当然实现的时候不用这样)。就是说,最小值和次小值不会处于同一颗子树上  回复  更多评论   

# re: The 36th ACM/ICPC Asia Regional Dalian Online Contest 大连2011ICPC网络赛 个人题解 2011-09-13 22:05 demo

ans2=min(ans2,1);这句直接ans2=1;就行了吧?  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年7月>
30123456
78910111213
14151617181920
21222324252627
28293031123
45678910

导航

统计

公告

统计系统

留言簿(1)

随笔分类(227)

文章分类(2)

OJ

最新随笔

搜索

积分与排名

最新评论

阅读排行榜