【noip 2015】普及组

T1.金币

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 using namespace std;
 5 int k;
 6 long long ans;
 7 int main()
 8 {
 9     scanf("%d",&k);
10     int cnt=1;
11     while(k)
12     {
13         for(int i=1;i<=cnt;i++)
14         {
15             if(k==0)break;
16             ans+=cnt;k--;
17         }
18         cnt++;
19         if(k==0)break;
20     }
21     printf("%lld",ans);
22     return 0;
23 }

View Code

T2.扫雷游戏

题目链接

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 using namespace std;
 5 const int xx[8]={-1,0,1,-1,1,-1,0,1},yy[8]={-1,-1,-1,0,0,1,1,1};
 6 int n,m;
 7 char s[105][105];
 8 int count(int x,int y)
 9 {
10     int num=0;
11     for(int i=0;i<8;i++)
12     {
13         int xi=x+xx[i],yi=y+yy[i];
14         if(xi<0||xi>=n||yi<0||yi>=m)continue;
15         if(s[xi][yi]=='*')num++;
16     }
17     return num;
18 }
19 int main()
20 {
21     scanf("%d%d",&n,&m);
22     for(int i=0;i<n;i++)scanf("%s",s[i]);
23     for(int i=0;i<n;i++,printf("
"))
24         for(int j=0;j<m;j++)
25         {
26             if(s[i][j]=='*')printf("*");
27             else printf("%d",count(i,j));
28         }
29     return 0;
30 }

View Code

T3.求和

题目链接

仔细读题之后我们会发现，我们枚举的过程其实跟y没什么关系……

但因为题目限定了x+z=2*y，即x+z为偶数，所以x和z必须同奇或同偶。

所以分颜色分奇偶存一下就好了✔

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<vector>
 5 using namespace std;
 6 const int N=100050;
 7 long long ans;
 8 int n,m,siz,color,num[N];
 9 vector<int>a[N][2];
10 int read()
11 {
12     int x=0,f=1;char c=getchar();
13     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
14     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
15     return x*f;
16 }
17 int main()
18 {
19     n=read();m=read();
20     for(int i=1;i<=n;i++)num[i]=read();
21     for(int i=1;i<=n;i++)
22     {
23         color=read();
24         a[color][i%2].push_back(i);
25     }
26     for(int i=1;i<=m;i++)
27     {
28         for(int t=0;t<2;t++)
29         {
30             siz=a[i][t].size();
31             for(int j=0;j<siz;j++)
32                 for(int k=j+1;k<siz;k++)
33                 {
34                     int x=a[i][t][j],z=a[i][t][k];
35                     ans=(ans+(long long)(x+z)*(num[x]+num[z]))%10007;
36                 }
37         }
38     }
39     printf("%lld",ans);
40     return 0;
41 }

View Code

T4.推销员

题目链接

维护两个大根堆，一个存各个住户的距离*2+疲劳值，另一个存各个住户的疲劳值；每次取出堆顶元素，将较大的那一个累加进答案里。

注意判断是否合法：假设当前走到的距离最远的住户为x；则直接累加住户i的疲劳值需要满足的条件为：s[i]<=s[x]；累加住户i的距离*2+疲劳值需要满足的条件为：s[i]>s[x]，且累加时记得减去s[x]*2。

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<queue>
 5 using namespace std;
 6 const int N=100050;
 7 struct node
 8 {
 9     int w,pos;
10     bool operator <(const node& a)const{return w<a.w;}
11 }q2[N],r1,r2;
12 priority_queue<node>q1;
13 int n,cnt,cut,tail,s[N],t[N];
14 bool f[N];
15 long long ans;
16 int read()
17 {
18     int x=0,f=1;char c=getchar();
19     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
20     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
21     return x*f;
22 }
23 int main()
24 {
25     n=read();cnt=n;tail=n;
26     for(int i=1;i<=n;i++)s[i]=read();
27     for(int i=1;i<=n;i++)
28     {
29         t[i]=read();
30         q2[i].w=s[i]*2+t[i];q2[i].pos=i;
31     }
32     sort(q2+1,q2+n+1);
33     while(cnt)
34     {
35         if(tail)r2=q2[tail],tail--;
36         else r2=(node){0,n+1};
37         if(r2.pos<=cut)continue;
38         if(!q1.empty())r1=q1.top(),q1.pop();
39         else r1=(node){0,0};
40         if(r1.w>r2.w-2*s[cut])
41         {
42             ans+=r1.w;
43             if(r2.pos!=n+1)tail++;
44         }
45         else
46         {
47             ans+=r2.w-2*s[cut];
48             for(int i=cut+1;i<r2.pos;i++)q1.push((node){t[i],i});
49             if(r1.pos!=0)q1.push(r1);
50             cut=r2.pos;
51         }
52         printf("%lld
",ans);cnt--;
53     }
54     return 0;
55 }

View Code