FJUTOJ-周赛2016-11-25

注：fjutoj基本每周都有一次周赛，欢迎大家都来参加！

网址：http://59.77.139.92/ 或 acm.fjut.edu.cn

A题

题意：一年中，每个月有可能亏x 元，有可能赚y 元，每连续的五个月加起来都亏钱，问一年最多赚多少钱，如果不能赚钱，输出"Deficit"。

思路：

　　贪心的思路，五个月中亏钱的月份放后面去，并且使得五个月加起来亏钱最少，因此共有4种情况：

　　x y y y y x y y y y x y

　　x x y y y x x y y y x x

　　x x x y y x x x y y x x

　　x x x x y x x x x y x x

　　用if判断一下即可

 1 #include
 2 #include<string.h>
 3 #include
 4 #include
 5 #include<set>
 6 #include

B题

题意：规定了两种日历的格式，给出第一个日历日期，要求转化成第二种。

思路：简单题，考验新生的代码实现能力，并不需要什么思路，略过。

 1 #include
 2 #include

C题

题意：字符串比较，第一个字符串多包含了*、？，*可以替换为任意多个任意字符，？可以替换为1个任意字符。

思路：数据量大时，用AC自动机做，因为该题数据量小，所以是简单题，递归一下更方便

 1 #include
 2 using namespace std;
 3 
 4 char head[100], s[100];
 5 bool dfs(int i, int j)
 6 {
 7   if(head[i]==0 && s[j]==0) return true;
 8   else if(head[i]==0) return false;
 9   else if(s[j]==0)
10   {
11     for(;head[i]!=0 && head[i]=='*';i++);
12     if(head[i]!=0) return false;
13     else return true;
14   }
15   if('a'<=head[i] && head[i]<='z')
16   {
17     if(s[i]!=head[j]) return false;
18     else return dfs(i+1, j+1);
19   }
20   else if(head[i]=='?') return dfs(i+1, j+1);
21   else
22   {
23     int k;
24     for(k=i;head[k];k++)
25     {
26       if(head[k]!='*') break;
27     }
28     if(head[k]==0) return true;
29     bool ret=false;
30     for(;s[j] && !ret;j++)
31     {
32       ret=dfs(k, j);
33     }
34     return ret;
35   }
36 }
37 
38 int main()
39 {
40   while(~scanf("%s",head))
41   {
42     int n;
43     scanf("%d",&n);
44     int co=0;
45     while(n--)
46     {
47       scanf("%s",s);
48       if(dfs(0,0)) co++;
49     }
50     printf("%d\n",co);
51   }
52   return 0;
53 }

D题

题意：有一个坐标系，坐标系上有n个点，在同一行或同一列上的任意两点称为关联的，并且关联属性是可传递的，即A和B关联，B和C关联，则可认为A和C关联，现在问图中是否任意两点都是关联的。

n>=2 && n<=50万

每个点的坐标x、y满足 1<=x、y<=50000

思路：并查集，横、纵坐标最多50000，可以先对所有点按横坐标排序，然后遍历一遍，如果两点横坐标相同，他们的纵坐标就是一组的。

 1 #include
 2 #include<string.h>
 3 #include
 4 using namespace std;
 5 #define N 500010
 6 
 7 int fa[N];
 8 int find(int x)
 9 {
10   int p=x;
11   while(p!=fa[p]) p=fa[p];
12   int q;
13   while(fa[x]!=p)
14   {
15     q=fa[x];
16     fa[x]=p;
17     x=q;
18   }
19   return p;
20 }
21 void join(int x,int y)
22 {
23   int fx=find(x);
24   int fy=find(y);
25   if(fx!=fy) fa[fx]=fy;
26 }
27 
28 struct Node
29 {
30   int x,y;
31 }v[N];
32 
33 bool cmp(Node a,Node b)
34 {
35   if(a.x!=b.x) return a.x>b.x;
36   else return a.y<b.y;
37 }
38 
39 bool vis[N];
40 int main()
41 {
42   int n;
43   while(scanf("%d",&n)!=EOF)
44   {
45     memset(vis,0,sizeof(vis));
46     for(int i=0;i)
47     {
48       scanf("%d%d",&v[i].x,&v[i].y);
49       if(v[i].y>50000) while(1);
50       vis[v[i].y]=1;
51     }
52     for(int i=1;i<=50000;i++) fa[i]=i;
53     sort(v,v+n,cmp);
54     int prex=-1, prey=-1;
55     for(int i=0;i)
56     {
57       if(v[i].x!=prex)
58       {
59         prex=v[i].x;
60         prey=v[i].y;
61       }
62       else
63       {
64         join(prey, v[i].y);
65       }
66     }
67     int co=0;
68     for(int i=1;i<=50000;i++)
69     {
70       if(vis[i])
71       {
72         if(fa[i]==i) co++;
73       }
74     }
75     if(co==1) printf("YES\n");
76     else printf("NO\n");
77   }
78   return 0;
79 }

E题

题意：给n个数，有m次询问，每次询问提供一个区间[l,r]，每次求一个x使得最小。

思路：划分树，基本是模板题了，略过。

 1 #include
 2 #include<string.h>
 3 #include
 4 using namespace std;
 5 #define N 100010
 6 #define LL long long
 7 int sorted[N];    //排序好的数组
 8 int num[20][N];   //num[i] 表示i前面有多少个点进入左孩子
 9 LL sum[20][N];
10 int val[20][N];   //20层,每一层元素排放，0层就是原数组
11 void build(int l,int r,int ceng)
12 {
13   if(l==r) return ;
14   int mid=(l+r)/2,isame=mid-l+1;  //isame保存有多少和sorted[mid]一样大的数进入左孩子
15   for(int i=l;i<=r;i++) if(val[ceng][i];
16   int ln=l,rn=mid+1;   //本结点两个孩子结点的开头，ln左
17   for(int i=l;i<=r;i++)
18   {
19     if(i==l) num[ceng][i]=0, sum[ceng][i]=0;
20     else num[ceng][i]=num[ceng][i-1], sum[ceng][i]=sum[ceng][i-1];
21     if(val[ceng][i]0)
22     {
23       val[ceng+1][ln++]=val[ceng][i];
24       num[ceng][i]++;
25       sum[ceng][i]+=val[ceng][i];
26       if(val[ceng][i]==sorted[mid]) isame--;
27     }
28     else
29     {
30       val[ceng+1][rn++]=val[ceng][i];
31     }
32   }
33   build(l,mid,ceng+1);
34   build(mid+1,r,ceng+1);
35 }
36 LL ans;
37 LL look(int ceng,int sl,int sr,int l,int r,int k,LL he)
38 {
39   if(sl==sr) return val[ceng][sl];
40   int ly; LL sy;
41   if(l==sl) ly=0,sy=0;
42   else ly=num[ceng][l-1],sy=sum[ceng][l-1];
43   int tolef=num[ceng][r]-ly;
44   LL ret;
45   if(tolef>=k)
46   {
47     ret = look(ceng+1,sl,(sl+sr)/2,sl+ly,sl+num[ceng][r]-1,k,sum[ceng][r]-sy);
48     ans += (he-sum[ceng][r]+sy)-ret*(r-l+1-tolef);
49   }
50   else
51   {
52     int lr = (sl+sr)/2 + 1 + (l-sl-ly);
53     ret = look(ceng+1,(sl+sr)/2+1,sr,lr,lr+r-l+1-tolef-1,k-tolef,he-sum[ceng][r]+sy);
54     ans += ret*tolef-sum[ceng][r]+sy;
55   }
56   return ret;
57 }
58 
59 LL pre[N];
60 int main()
61 {
62   int cas=1,t,n,m,l,r;
63   scanf("%d",&t);
64   while(t--)
65   {
66     printf("Case #%d:\n",cas++);
67     scanf("%d",&n);
68     pre[0]=0;
69     for(int i=1;i<=n;i++)
70     {
71       scanf("%d",&val[0][i]);
72       sorted[i]=val[0][i];
73       pre[i]=pre[i-1]+val[0][i];
74     }
75     sort(sorted+1,sorted+n+1);
76     build(1,n,0);
77     scanf("%d",&m);
78     while(m--)
79     {
80       scanf("%d%d",&l,&r);
81       l++, r++;
82       ans=0;
83       look(0,1,n,l,r,(r-l+2)/2,pre[r]-pre[l-1]);
84       printf("%I64d\n",ans);
85     }
86     printf("\n");
87   }
88   return 0;
89 }

总结：A题考逻辑能力，B题考代码能力，C题需要更高的代码能力，D题考简单的数据结构，E题考知识面。