NOI1997
D1T2 最优乘车
单源最短路问题。
考输入。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
using namespace std;
int read(){
int x=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='\n'||c==EOF)return -1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return x;
}
bool mp[505][505]={0};
int n,m,q[5005],f=0,r=0,d[505];
void solve(){
q[r++]=0,d[0]=-1;
int h,v;
while(r-f){
h=q[f++];
for(v=0;v<n;v++)
if(mp[h][v]&&d[v]>d[h]+1)d[v]=d[h]+1,q[r++]=v;
}
}
int main(){
m=read(),read();n=read(),read();
fill(d,d+n,10000000);
int i,j,u,v;
for(i=0;i<m;i++){
j=0;while((v=read())>0)q[j++]=v;
for(u=0;u<j;u++)
for(v=u+1;v<j;v++)
mp[q[u]-1][q[v]-1]=1;
}
solve();
if(d[n-1]>=1000000)printf("NO\n");
else printf("%d\n",d[n-1]);
return 0;
}
NOI1998
D1T1 个人所得税
模拟即可。
开数组存每个员工每个月的收入，最后再计算；遇到单个的就直接计算。
本题读入很神奇，需注意。
还有就是负数的处理问题，应交税的部分不能为负。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
using namespace std;
typedef long long ll;
int m,money[50005][20]={0};
char typ[10],tim[10],PAY[]="PAY",INC[]="INCOME";
double ans=0,pay_l[]={0,500,2000,5000,20000,40000,60000,80000,100000,999999999}
,inc_l[]={0,20000,50000,999999999};
void init(){
scanf("%d",&m);
}
double Count_pay(int pr){
double left=max(0,pr-800),_ans=0;
for(int i=1;i<=9;i++)
if(left<pay_l[i]){
_ans+=i*0.05*(left-pay_l[i-1]);
break;
}else _ans+=i*0.05*(pay_l[i]-pay_l[i-1]);
return _ans;
}
double Count_income(int pr){
double left,_ans=0;
left=(pr>4000)?(pr*0.8):(max(0,pr-800));
for(int i=1;i<=3;i++){
if(left<inc_l[i]){
_ans+=(i+1)*0.1*(left-inc_l[i-1]);
break;
}else _ans+=(i+1)*0.1*(inc_l[i]-inc_l[i-1]);
}
return _ans;
}
void solve(){
int id,pr,mon;
for(;;){
scanf("%s",typ);
if(typ[0]=='#')break;
scanf("%d%s%d",&id,tim,&pr);
if(!strcmp(PAY,typ)){
if(tim[1]=='/')mon=tim[0]-'0';
else mon=10*(tim[0]-'0')+tim[1]-'0';
money[id][mon]+=pr;
}else{
ans+=Count_income(pr);
}
}
for(int i=1;i<=m;i++)
for(int j=1;j<=12;j++)
if(money[i][j])
ans+=Count_pay(money[i][j]);
printf("%.2lf\n",ans);
}
int main(){
init();
solve();
return 0;
}
NOI2000
D1T1 瓷片项链
二次函数。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
using namespace std;
int v,v0;
int main(){
if((v%v0==0&&v%(v0+v0))||v==0)
printf("0\n");
else {
double a=v,b=v0,ans,d=v/(v0+v0);
if(ceil(d)-d>d-floor(d))
ans=floor(d);
else ans=ceil(d);
printf("%d\n",(int)ans);
}
return 0;
}
D1T3 古城之谜
这题怎么想的。。。
看了byvoid的题解还是有点晕晕乎乎。
要先对给出的形式进行简化。
句子：是名词、动词短语交替出现的，且开头必定为名词短语。
名词短语：相当于任意多个副词+名词。
动词短语：相当于任意多个副词+动词。
考虑刻画状态，字母要算进去，当前词性要算进去，还要考虑最少的句子数和单词数。
所以设$f(i,j,k)$表示前$i$个字母，最后一个单词词性为$j$，组成$k$个句子的最小单词数量。$j$有$3$种，用$0,1,2$表示名，动，副。但是还要考虑到副词的链接问题。所以加一种情况：$j=3$，表明是副词，并且前面最近的非副词是动词。$j=2$时前面最近的非副词是名词。
然后就大力转移即可。
直接开数组会MLE，但是可以发现$k$的转移来源只会是$k$和$k-1$，所以用滚动数组压掉这一维。
匹配串我用的是hash，大概不会被卡掉…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
using namespace std;
typedef unsigned long long ll;
int read(){
int f=1,x=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
int n,len,f[5005][4][2],maxl=0;
char word[1005][25],tex[50005];
ll hsh[50005],Pow[50005];
bool t1[10000007],t2[10000007],t3[10000007];
ll getHash(int i,int j){
return hsh[j]-(hsh[i-1]*Pow[j-i+1]);
}
void init(){
n=read();
int l;ll Hash;
for(int i=1;i<=n;i++){
scanf("%s",word[i]);
l=strlen(word[i]),Hash=0,maxl=max(maxl,l-2);
for(int j=2;j<l;j++)
Hash=Hash*137ull+(ll)word[i][j]+157ull;
if(word[i][0]=='n')t1[Hash%Mod]=1;
if(word[i][0]=='v')t2[Hash%Mod]=1;
if(word[i][0]=='a')t3[Hash%Mod]=1;
}
scanf("%s",tex+1);
len=strlen(tex+1)-1,hsh[0]=0,Pow[0]=1;
for(int i=1;i<=len;i++)
hsh[i]=hsh[i-1]*137ull+(ll)tex[i]+157ull,Pow[i]=Pow[i-1]*137ull;
}
void solve(){
memset(f,0x3f,sizeof(f));
f[0][0][0]=0;
int B,B_,ans1,ans2;
ll tmp;
for(int k=1;k<=len;k++){
B=(k&1),B_=B^1;
for(int i=1;i<=len;i++){
f[i][0][B]=f[i][1][B]=f[i][2][B]=f[i][3][B]=0x3f3f3f3f;
for(int t=i;t>i-maxl&&t>=1;t--){
tmp=getHash(t,i)%Mod;
if(t1[tmp]){
int &T=f[i][0][B];
T=min(T,min(f[t-1][1][B]+1,f[t-1][3][B]+1));
T=min(T,min(f[t-1][0][B_]+1,f[t-1][1][B_]+1));
}
if(t2[tmp]){
int &T=f[i][1][B];
T=min(T,min(f[t-1][0][B]+1,f[t-1][2][B]+1));
}
if(t3[tmp]){
int &T=f[i][2][B];
T=min(T,min(f[t-1][0][B]+1,f[t-1][2][B]+1));
T=min(T,f[t-1][0][B_]+1);
int &T2=f[i][3][B];
T2=min(T2,min(f[t-1][1][B]+1,f[t-1][3][B]+1));
T2=min(T2,min(f[t-1][0][B_]+1,f[t-1][1][B_]+1));
}
}
}
if(f[len][0][B]<INF||f[len][1][B]<INF){
ans1=k,ans2=min(f[len][0][B],f[len][1][B]);
break;
}
}
printf("%d\n%d\n",ans1,ans2);
}
int main(){
init();
solve();
return 0;
}
D2T1 单词查找树
trie树模板题？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
using namespace std;
typedef long long ll;
int trie[100005][29]={0};
char wd[1005];
int read(){
int f=1,x=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
void solve(){
int ans=1,p;
char *s;
while(~scanf("%s",wd)){
p=1;
for(s=wd;*s;s++){
if(!trie[p][*s-'A'])
trie[p][*s-'A']=++ans;
p=trie[p][*s-'A'];
}
}
printf("%d\n",ans);
}
int main(){
solve();
return 0;
}
D2T2 青蛙过河
设$f(h,k)$为答案。
则显然的是$f(0,k)=k+1$。
我们加一个石墩，那么可以先把最上面一波青蛙送到新加的上面去，然后
把下面那一拨送到对岸，再把石墩上的送走。
所以$f(1,k)=2f(0,k)$。
再加一个。我们又把一波青蛙送到其中一个石墩上，然后问题变成了$f(1,k)$的形式，
所以$f(2,k)=2f(1,k)$。
换言之，加一个石墩，送青蛙的能力就增强一倍。
所以$f(h,k)=2^h (k+1)$。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
using namespace std;
typedef long long ll;
ll h,k;
void init(){
scanf("%lld%lld",&h,&k);
}
void solve(){
printf("%lld\n",(k+1)*(1<<h));
}
int main(){
init();
solve();
return 0;
}
D2T3 算符破译
NOI2001
D1T1 食物链
设$a,2a,3a$分别表示$a$属于$A,B,C$。
则
对于1，判断$a$与$2b$和$a$与$3b$是否在同一集合
对于2，判断$a$吃不吃自己与$b$吃不吃$a$
即可。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
int rank[150010],parent[150010],t,ans=0,k,n,x,y;
int same(int a,int b),find(int a);
void init(int n),joint(int x,int y);
void init(int n){
int i;for(i=1;i<=n;i++){
parent[i]=i;
rank[i]=0;
}
}void joint(int x,int y){
int a=find(x),b=find(y);
if(a==b)return;
if(rank[a]<rank[b]){
parent[a]=b;
}else{
parent[b]=a;
if(rank[a]==rank[b])rank[a]++;
}
}int find(int a){
if(parent[a]==a)return a;
else return (parent[a]=find(parent[a]));
}int same(int a,int b){return find(a)==find(b);}
int main(){
scanf("%d%d",&n,&k);int i;
init(n*3);for(i=0;i<k;i++){
scanf("%d%d%d",&t,&x,&y);
if(x>n||y>n||x<1||y<1)ans++;
else{
if(t==1){
if(same(x,y+n)||same(x,y+2*n))ans++;
else {joint(x,y);joint(x+n,y+n);joint(x+n*2,y+n*2);}
}else{
if(same(x,y+2*n)||same(x,y))ans++;
else{
joint(x,y+n);joint(x+n,y+2*n);joint(x+n*2,y);
}
}
}
}printf("%d\n",ans);
return 0;
}
D1T2 反正切函数的应用
$O(\sqrt n)$乱搞。
利用$(a-b)(a-c)=a^2+1$1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
using namespace std;
typedef unsigned int uint;
uint a,ans=4000000000u,d;
int main(){
scanf("%u",&a);
d=a*a+1;
for(uint i=1;i*i<=d;i++)
if(d%i==0)ans=min(ans,a+a+i+d/i);
printf("%u\n",ans);
return 0;
}
D1T3 聪明的打字员
标准的广搜。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
using namespace std;
typedef long long ll;
int read(){
int f=1,x=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
char vis[1000000][6]={0};
int S,T,ans[1000005][6],ten[10];
queue<int> q1,q2;
//000000-999999
int ptoi(int *L){
int res=0;
for(int i=0;i<6;i++)res=res*10+L[i];
return res;
}
void itop(int *L,int x){
for(int i=5;i>=0;i--)L[i]=x%10,x/=10;
}
void init(){
S=read(),T=read();
memset(ans,0x3f,sizeof(ans));
ans[S][0]=0;
ten[5]=1;
for(int i=4;i>=0;i--)ten[i]=ten[i+1]*10;
}
void solve(){
vis[S][0]=1,q1.push(S),q2.push(0);
int h,pos,permu[10],Ans=INF,now,to;
while(!q1.empty()){
h=q1.front(),q1.pop(),pos=q2.front(),q2.pop();
if(h==T)break;
now=ans[h][pos],itop(permu,h);
if(pos&&!vis[h][pos-1])//left
vis[h][pos-1]=1,ans[h][pos-1]=now+1,
q1.push(h),q2.push(pos-1);
if(pos!=5&&!vis[h][pos+1])//right
vis[h][pos+1]=1,ans[h][pos+1]=now+1,
q1.push(h),q2.push(pos+1);
if(permu[pos]!=9){//up
to=h+ten[pos];
if(!vis[to][pos])
vis[to][pos]=1,ans[to][pos]=now+1,
q1.push(to),q2.push(pos);
if(to==T)break;
}
if(permu[pos]){//down
to=h-ten[pos];
if(!vis[to][pos])
vis[to][pos]=1,ans[to][pos]=now+1,
q1.push(to),q2.push(pos);
if(to==T)break;
}
if(pos&&permu[0]!=permu[pos]){
to=h-permu[0]*ten[0]-permu[pos]*ten[pos]+permu[0]*ten[pos]+permu[pos]*ten[0];
if(!vis[to][pos])
vis[to][pos]=1,ans[to][pos]=now+1,
q1.push(to),q2.push(pos);
if(to==T)break;
}
if(pos!=5&&permu[5]!=permu[pos]){
to=h-permu[5]*ten[5]-permu[pos]*ten[pos]+permu[5]*ten[pos]+permu[pos]*ten[5];
if(!vis[to][pos])
vis[to][pos]=1,ans[to][pos]=now+1,
q1.push(to),q2.push(pos);
if(to==T)break;
}
}
for(int i=0;i<6;i++)Ans=min(Ans,ans[T][i]);
printf("%d\n",Ans);
}
int main(){
init();
solve();
return 0;
}
D2T1 炮兵阵地
标准的状压DP。
D2T2 方程的解数
meet in the middle。
拆成两半，$O(M^3)$枚举+核对。
用map会MLE，干脆hash。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
using namespace std;
typedef long long ll;
int n,m;
ll k[15],p[15],ppow[155][40]={0},half,ans=0;
ll LIM=2147483647;
int hsh[4000060],cnt[4000060];
bool vis[4000060]={0};
void init(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%lld%lld",&k[i],&p[i]);
for(ll i=1;i<=m;i++){
ppow[i][0]=1;
ll lim=1;
for(int j=1;j<=35;j++){
lim*=i;
if(lim>=LIM)break;
ppow[i][j]=ppow[i][j-1]*i;
}
}
}
int locate(int val){
int q=abs(val);
for(q%=P;vis[q]&&hsh[q]!=val;q=(q==P-1)?0:q+1);
return q;
}
void build(int at,ll val){
if(at>half){
int loc=locate((int)val);
cnt[loc]++,hsh[loc]=(int)val,vis[loc]=1;
return ;
}
for(int i=1;i<=m;i++){
if(!ppow[i][p[at]])break;
ll lim=val+ppow[i][p[at]]*k[at];
if(lim>=LIM||lim<=-LIM)break;//爆了
build(at+1,lim);
}
}
void Search(int at,ll val){
if(at==n+1){
int _val=(int)(-val);
int loc=locate(_val);
if(hsh[loc]==_val)ans+=cnt[loc];
return ;
}
for(int i=1;i<=m;i++){
if(!ppow[i][p[at]])break;
ll lim=val+ppow[i][p[at]]*k[at];
if(lim>=LIM||lim<=-LIM)break;//爆了
Search(at+1,lim);
}
}
void solve(){
half=n/2;
build(1,0);
Search(half+1,0);
printf("%d\n",ans);
}
int main(){
init();
solve();
return 0;
}
D2T3 陨石的秘密
题目链接
可以发
现SS表达式的定义是递归形式的，而且SS表达式形成了一个树形结构（有深度，还有儿子）。
设$f(i,j,k,d)$为$i$对大括号，$j$对中括号，$k$对小括号，树深度$<=d$的方案总数。
对于同一层而言，决策有：
- 分出一支，深度变大。
- 同一层上增加。
对于第一种情况，我们再加一个状态：设$g(i,j,k,d)$为$i$对大括号，$j$对中括号，$k$对小括号，树深度$\le d$，且表达式构成一棵树的方案总数。他从$f$转移而来，决策是给$f$加一个根。
这样就可以转移了。
初始：$f(0,0,0,0…D)=1$。
答案：（相当于容斥）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
using namespace std;
typedef long long ll;
int read(){
int f=1,x=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
int l1,l2,l3,D,f[11][11][11][31]={0},g[11][11][11][31]={0};
char vis1[11][11][11][31]={0},vis2[11][11][11][31]={0};
int dp_g(int a,int b,int c,int d);
int dp_f(int a,int b,int c,int d);
int dp_g(int a,int b,int c,int d){
if(vis2[a][b][c][d])return g[a][b][c][d];
int t=0;
if(!a&&!b&&c>=1)(t+=dp_f(a,b,c-1,d-1))%=Mod;
if(!a&&b>=1)(t+=dp_f(a,b-1,c,d-1))%=Mod;
if(a>=1)(t+=dp_f(a-1,b,c,d-1))%=Mod;
vis2[a][b][c][d]=1;
return (g[a][b][c][d]=t);
}
int dp_f(int a,int b,int c,int d){
if(vis1[a][b][c][d])return f[a][b][c][d];
int t=0;
for(int i=0;i<=a;i++)
for(int j=0;j<=b;j++)
for(int k=0;k<=c;k++)
if(i||j||k)(t+=dp_g(i,j,k,d)*dp_f(a-i,b-j,c-k,d))%=Mod;
vis1[a][b][c][d]=1;
return (f[a][b][c][d]=t);
}
void init(){
l1=read(),l2=read(),l3=read(),D=read();
for(int i=0;i<=D;i++)
vis1[0][0][0][i]=1,f[0][0][0][i]=1,
vis2[0][0][0][i]=1,g[0][0][0][i]=0;
}
void solve(){
printf("%d\n",(dp_f(l1,l2,l3,D)-dp_f(l1,l2,l3,D-1)+Mod)%Mod);
}
int main(){
init();
solve();
return 0;
}
NOI2002
D1T2 调皮的小孩
（题目暂缺）
显然你最多只能问一个人$2$遍。
显然你问裁判同样问题$2$次他就会自爆。
那就分类讨论。先随便找个人，然后对其他人问他是不是0队的。
- $N$个人Yes$M$个No，那么这个人就有可能是0队的。
（1）$N\neq M$，他就是0队的。
（2）$N=M$，让他问1队的任意一个人是不是1队的$2$次，答案一样这个人就是0队的，反之就是裁判。 - $N+1$个人No$M-1$个人Yes，那么这个人是1队的，去另外$N+1$个人问他是不是1队的即可。
- $N$个人No$M$个人Yes，$N\neq M$他就是裁判，$N=M$就套用1的解决方法。