noip 2012

  • P1079 Vigenère 密码
  • P1080 国王游戏
  • P1081 开车旅行
  • P1082 同余方程
  • P1083 借教室
  • P1084 疫情控制

    P1079 Vigenère 密码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/*
ID: ylx14271
PROG:
LANG: C++
*/
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#define LL unsigned long long
using namespace std;
string sa,sb;
int la,lb,i,k;
//k:sb目前搜到的位置
int main()
{
cin>>sa;
cin>>sb;
la=sa.size();
lb=sb.size();
for (i=0;i<la;i++)
{
if ('A'<=sa[i]&&sa[i]<='Z') sa[i]=sa[i]+32;
}
for (i=0;i<lb;i++)
{
if ('A'<=sb[i]&&sb[i]<='Z') sb[i]=((sb[i]-sa[k]+97-65)%26+26)%26+65;
else sb[i]=((sb[i]-sa[k])%26+26)%26+97;
k=(k+1)%la;
}
cout<<sb;
return 0;
}

P1080 国王游戏

贪心部分:
对于第 $i$个大臣和第 $j$ 个大臣:
如果第 $i$ 个大臣放第 $j$ 个大臣前面对答案的贡献小些,那么第 $i$ 个大臣就放第 $j$ 个大臣前面
所以就是使 $a[i].x/a[j].y<a[j].x/a[i].y$

然后高精度部分压位,这样快得多,20ms,

乘法部分相当于高精度乘低精度

除法部分相当于高精度除低精度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include<bits/stdc++.h>
using namespace std;
int read()
{
char s;
int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
if(s==EOF)exit(0);
if(s=='-')base=-1,s=getchar();
while(s>='0'&&s<='9')
{
k=k*10+(s-'0');
s=getchar();
}
return k*base;
}
void write(int x)
{
if(x<0)
{
putchar('-');
write(-x);
}
else
{
if(x/10)write(x/10);
putchar(x%10+'0');
}
}
int n,A,B;
struct node
{
int x,y;
} a[1010];
bool cmp(node aa,node bb)
{
if (aa.x*aa.y==bb.x*bb.y) return aa.y<bb.y;
return (aa.x*aa.y)<(bb.x*bb.y);
}
int sum[1010];
int ans[1010],ls;
int p[1010],lp;
int m;//sum长度
int P;
bool Max()//比大小,ans>p: true
{
int i=1;
while (p[i]==0&&i<=lp) i++;//去掉前面的0
int j=1;
while (ans[j]==0&&j<=ls) j++;
if (lp-i+1>ls-j+1) return false;//p的位数>ans的位数
if (lp-i+1<ls-j+1) return true;
while (i<=lp&&j<=ls)//一位一位的比较
{
if (p[i]<ans[j]) return true;
if (p[i]>ans[j]) return false;
i++;
j++;
}
return false;
}
void cheng(int d)
{
for (int i=1;i<=m;i++)
sum[i]*=a[d].x;//高精度乘法
for (int i=1;i<=m;i++)//进位
{
sum[i+1]+=sum[i]/10000;
sum[i]%=10000;
}
if (sum[m+1]!=0) m++;
}
void div(int d)
{
memset(ans,0,sizeof(ans));
ls=1;
while (m>0&&sum[m]==0) m--;//去掉前导0
P=0;
int flag=0;
for (int i=m;i>=1;i--)//高精度除法(模拟竖式)
{
P=P*10000+sum[i];
ans[++ls]=P/a[d].y;
if (ans[ls]==0&&!flag) ls--; else flag=1;
P%=a[d].y;
}
}
int main()
{
n=read();
A=read();
B=read();
for (int i=1;i<=n;i++) a[i].x=read(),a[i].y=read();
sort(a+1,a+n+1,cmp);
m=1;
sum[1]=A;
for (int i=1;i<=n;i++)
{
div(i);
if (Max())
{
lp=ls;
memcpy(p,ans,sizeof(ans));
}
cheng(i);
}
int i=0;
while (i<=lp&&p[i]==0) i++;
printf("%d",p[i]);i++;
for (;i<=lp;i++)//输出
{
if (0<=p[i]&&p[i]<=9) printf("000%d",p[i]);else
if (10<=p[i]&&p[i]<=99) printf("00%d",p[i]);else
if (100<=p[i]&&p[i]<=999) printf("0%d",p[i]);else
printf("%d",p[i]);
}
return 0;
}

P1081 开车旅行

P1082 同余方程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<set>  
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#define LL unsigned long long
using namespace std;
long long a,b,x,y;
long long wochun(long long a,long long b,long long &x,long long &y)
{
if (b==0)
{
x=1;
y=0;
return a;
}
long long chun=wochun(b,a%b,x,y);
long long t=x;
x=y;
y=t-(a/b)*x;
return chun;
}
int main()
{
cin>>a>>b;
long long chun=wochun(a,b,x,y);
x=x%b;
while (x<0) x+=b;
cout<<x;
return 0;
}

P1083 借教室

二分+前缀和。
二分第一次出现问题的订单的编号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m;//天数,订单数
int a[1000010];
int d[1000010],s[1000010],t[1000010];
int c[1000000];//前缀
int ans;//结果
int l,r,mid;//二分用
int i;
bool check(int x)//找到第x组为止是否有一天出现负数
{
memset(c,0,sizeof(c));//清空前缀和数组
int j;
for (j=1;j<=x;j++)//求前缀和
{
c[s[j]]+=d[j];
c[t[j]+1]-=d[j];
}
for (j=1;j<=n;j++)//判断是否有一天教室不够用
c[j]+=c[j-1];
for (j=1;j<=n;j++)
if (c[j]>a[j]) return false;
return true;
}
int main()
{
scanf("%d%d",&n,&m);//读入
ans=23333333;
for (i=1;i<=n;i++) scanf("%d",&a[i]);
for (i=1;i<=m;i++) scanf("%d%d%d",&d[i],&s[i],&t[i]);
l=1;
r=m;
while (l!=r)
{
mid=(l+r)/2;
bool f=check(mid);
if (f==true)//前面没有出现教室不够用的情况就搜后面
{
l=mid+1;
}else
{
ans=min(ans,mid);//前mid组一定出现问题了但不一定就是第mid组最小,所以要更新答案
r=mid;
}
}
if (ans==23333333) cout<<0;//教室够用
else cout<<-1<<endl<<ans;//输出
return 0;
}

P1084 疫情控制