The 36th ACM/ICPC Asia Regional Shanghai Site —— Warmup 个人题解

好吧,做出来6题。。不想写详细的结题报告了,写个简略版的把
第一题,贪心,不用说
# include <cstdio>
using namespace std;
int main()
{
    int test;
    scanf("%d",&test);
    for(int t=1;t<=test;t++)
    {
       int n;
       long long c1,c2;
       scanf("%d%I64d%I64d",&n,&c1,&c2);
       long long last;
       scanf("%I64d",&last);
       long long total=2*c1+c2;
       for(int i=1;i<n;i++)
       {
           long long tmp;
           scanf("%I64d",&tmp);
           if((tmp-last-1)*c2<2*c1)
             total+=(tmp-last)*c2;
           else
              total+=c2+2*c1;
           last=tmp;
       }
       printf("Case #%d: %I64d\n",t,total);
    }
    return 0;
} 
第二题,BFS+位压缩,也不用说
# include <cstdio>
# include <cstring>
# include <queue>
using namespace std;
int n;
char str[2][20];
int len[1<<20];
queue<int> q;
inline bool getbit(int code,int n)
{
    return code&(1<<n);
}
int change(int code,int h1,int w1,int h2,int w2,char color)
{
    for(int i=h1;i<h2;i++)
        for(int j=w1;j<w2;j++)
            if(str[i][j]==color)
                code|=(1<<(2*j+i));
            else if(getbit(code,2*j+i))
                code-=(1<<(2*j+i));
    return code;
}
void print(int code)
{
    printf("\n");
    for(int i=0;i<n;i++)
        printf("%d ",getbit(code,2*i));
    printf("\n");
    for(int i=0;i<n;i++)
        printf("%d ",getbit(code,2*i+1));
    printf("\n");
}
int main()
{
    int test;
    scanf("%d",&test);
    for(int t=1;t<=test;t++)
    {
        scanf("%d%s%s",&n,str[0],str[1]);
        memset(len,-1,sizeof(len));
        while(!q.empty())
            q.pop();
        len[0]=0;
        q.push(0);
        int target=(1<<(2*n))-1;
        while(!q.empty())
        {
            int top=q.front();
            q.pop();
            //print(top);
            if(top==target) break;
            for(int i=0;i<n;i++)
            {
                if(!getbit(top,2*i))
                {
                         for(int w=1;w<=n-i;w++)
                         {
                             int newcode=change(top,0,i,1,i+w,str[0][i]);
                             if(len[newcode]==-1)
                                 len[newcode]=len[top]+1,q.push(newcode);
                             newcode=change(top,0,i,2,i+w,str[0][i]);
                             if(len[newcode]==-1)
                                 len[newcode]=len[top]+1,q.push(newcode);
                         }
                    
                }
                 if(!getbit(top,2*i+1))
                {
                        for(int w=1;w<=n-i;w++)
                             {
                                 int newcode=change(top,0,i,2,i+w,str[1][i]);
                                 if(len[newcode]==-1)
                                     len[newcode]=len[top]+1,q.push(newcode);
                                 newcode=change(top,1,i,2,i+w,str[1][i]);
                                 if(len[newcode]==-1)
                                     len[newcode]=len[top]+1,q.push(newcode);
                             }
                    
                }
            }
        }
        printf("Case #%d: %d\n",t,len[target]);

    }
    return 0;
}
第三题,想暴力+hash+树最小表示,悲剧的TLE,估计用stl效率太低了
赛后我用java写出来了,1A
  1 import java.io.*;
  2 import java.util.*;
  3 public class Main {
  4 
  5     /**
  6      * @param args
  7      */
  8     static int leg[]=new int[1<<15],p;
  9     static HashSet<String> refer[]=new HashSet[1<<15];
 10     static int g[]=new int[15],v[]=new int[50],nxt[]=new int[50],c,n;
 11     static boolean used[]=new boolean[15];
 12     static StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
 13     static int input() throws IOException
 14     {
 15         in.nextToken();
 16         return (int)in.nval;
 17     }
 18     static void insert(int a,int b)
 19     {
 20         v[c]=b;
 21         nxt[c]=g[a];
 22         g[a]=c++;
 23         v[c]=a;
 24         nxt[c]=g[b];
 25         g[b]=c++;
 26     }
 27     static boolean getbit(int bit,int pos)
 28     {
 29         return (bit&(1<<pos))!=0;
 30     }
 31     static void chk(int now,int pre,int code)
 32     {
 33         used[now]=true;
 34         for(int i=g[now];i!=-1;i=nxt[i])
 35             if(v[i]!=pre&&getbit(code,v[i]))
 36                 chk(v[i],now,code);
 37             
 38     }
 39     static boolean chk(int now,int code)
 40     {
 41         Arrays.fill(used,false);
 42         chk(now,now,code);
 43         for(int i=0;i<n;i++)
 44           if(getbit(code,i))
 45             if(!used[i])
 46                 return false;
 47         return true;
 48     }
 49     static String dfs(int now,int pre,int code)
 50     {
 51         ArrayList<String> tmp=new ArrayList<String>();
 52         for(int i=g[now];i!=-1;i=nxt[i])
 53             if(v[i]!=pre&&getbit(code,v[i]))
 54                 tmp.add(dfs(v[i],now,code));
 55         Collections.sort(tmp);
 56         StringBuffer ans=new StringBuffer("(");
 57         for(String i:tmp)
 58             ans.append(i);
 59         ans.append(")");
 60         return ans.toString();
 61     }
 62     public static void main(String[] args) throws IOException{
 63         int test=input();
 64         for(int i=0;i<(1<<15);i++)
 65             refer[i]=new HashSet<String>();
 66         for(int t =1;t<=test;t++)
 67         {
 68             p=0;
 69             c=0;
 70             Arrays.fill(g,-1);
 71             n=input();
 72             for(int i=1;i<n;i++)
 73               insert(input()-1,input()-1);
 74             for(int i=1;i<(1<<n);i++)
 75             {
 76                 int start=-1;
 77                 for(int j=0;j<n&&start==-1;j++)
 78                     if(getbit(i,j))
 79                         start=j;
 80                 if(!chk(start,i)) continue;
 81                 leg[p++]=i;
 82                 refer[i].clear();
 83                 for(int j=start;j<n;j++)
 84                     if(getbit(i,j))
 85                         refer[i].add(dfs(j,j,i));
 86             }
 87             int total=0;
 88             for(int i=0;i<p;i++)
 89             {
 90                 boolean flag=true;
 91                 for(String ii:refer[leg[i]])
 92                 {
 93                     for(int j=0;j<i&&flag;j++)
 94                         if(refer[leg[j]].contains(ii))
 95                             flag=false;
 96                     if(!flag) break;
 97                 }
 98                 if(flag) total++;
 99             }
100             System.out.println("Case #"+t+""+total);
101         }
102 
103     }
104 
105 }

第四题:不知道
第五题:我女友写的~恩,也是我们队数学最牛的~,思想不明。。
#include<iostream>
#include<stdio.h>
using namespace std;
int main()
{
    int m,t,k;
scanf("%d",&t);
    for(int i=1;i<=t;i++)
    {
      //cin>>m>>k;
      scanf("%d%d",&m,&k);
        printf("Case #%d: ",i);
        printf("%.8f\n",1.0/(m*k+k+1));
        //cout<<endl;
    }
    
}
第六、七题:不知道
第八题:简单字符串处理,MS上次复旦邀请赛也有这么一道关于URL的题目
 include <cstdio>
# include <cstdlib>
# include <cstring>
using namespace std;
char str[1024];
int main()
{
    int test;
    scanf("%d",&test);
    getchar();
    for(int t=1;t<=test;t++)
    {
        gets(str);
        int begin;
        for(begin=0;str[begin]!=':';begin++);
        begin+=3;
        for(int i=begin;str[i]!='\0';i++)
          if(str[i]==':'||str[i]=='/')
          {
             str[i]='\0';
             break;
          }
        printf("Case #%d: %s\n",t,str+begin);
        //puts(str+begin);
    }
    return 0;
}

第十题:数据结构的联合,首先大数组以人编号为第一关键字,click为第二关键字排序,用图中类似前向星的结构来存储第几个人的开始位置。然后就是扫描,这里一定要用链表,复杂度O(m),不然复杂度会高达o(mn),然后肯定TLE。话说。开始我用vector想省事,结果RE了。。复旦数据卡的太大了
# include <cstdio>
# include <algorithm>
# include <cstring>
# include <list>
using namespace std;
# define M 500005
# define N 100005
struct node
{
    int id,click,length;
    bool operator<(const node &pos) const
    {
        if(id!=pos.id) return id<pos.id;
        else return click>pos.click;
    }
}data[M];
int n,m,q;
int s[N];
long long ans[M];
list<int> li;
int main()
{
    int test;
    scanf("%d",&test);
    for(int t=1;t<=test;t++)
    {
        scanf("%d%d%d",&n,&m,&q);
        for(int i=0;i<m;i++)
            scanf("%d%d%d",&data[i].id,&data[i].click,&data[i].length);
        sort(data,data+m);
        memset(s,-1,sizeof(s));
        for(int i=0;i<m;i++)
            if(s[data[i].id]==-1)
                s[data[i].id]=i;
        int now=1;
        ans[0]=0;
        li.clear();
        for(int i=1;i<=n;i++)
            if(s[i]!=-1) li.push_back(i);
        while(!li.empty())
        {
            ans[now]=ans[now-1];
            for(list<int>::iterator i=li.begin();i!=li.end();)
            {
                ans[now]+=data[s[*i]].length;
                s[*i]++;
                if(s[*i]>=m||data[s[*i]].id!=data[s[*i]-1].id)
                    i=li.erase(i);
                else i++;
            }
            now++;
        }
        printf("Case #%d:\n",t);
        while(q--)
        {
            int num;
            scanf("%d",&num);
            if(num>=now) num=now-1;
            printf("%I64d\n",ans[num]);
        }
        
    }
    return 0;
}




posted on 2011-09-07 22:30 yzhw 阅读(569) 评论(2)  编辑 收藏 引用 所属分类: others

评论

# re: The 36th ACM/ICPC Asia Regional Shanghai Site —— Warmup 个人题解 2011-09-08 09:35 tjt

怎么突然又成了6题了呢~~  回复  更多评论   

# re: The 36th ACM/ICPC Asia Regional Shanghai Site —— Warmup 个人题解 2011-09-08 12:10 yzhw

@tjt
有一题当时算法对的,用C++没过。后来用java过掉了
呵呵~我不是说比赛时候做出6题  回复  更多评论   


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


<2011年9月>
28293031123
45678910
11121314151617
18192021222324
2526272829301
2345678

导航

统计

公告

统计系统

留言簿(1)

随笔分类(227)

文章分类(2)

OJ

最新随笔

搜索

积分与排名

最新评论

阅读排行榜