NOIP1996
提高T3 挖地雷
题目已经帮你拓扑排序完了，直接转移就可以。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;
int n,V,mp[25][25]={0},m[25],dp[25]={0},pre[25],ans[25],maxi=0,at;
int main(){
scanf("%d",&n);
int i,j;
fill(pre,pre+n,-1);//记录路径
for(i=0;i<n;i++)
scanf("%d",&m[i]);
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
scanf("%d",&mp[i][j]);
dp[0]=maxi=m[0],at=0;
for(i=1;i<n;i++){
for(j=i-1;j>=0;j--)
if(mp[j][i]&&dp[j]>=dp[i])
dp[i]=dp[j],pre[i]=j;
dp[i]+=m[i];
if(dp[i]>maxi)
maxi=dp[i],at=i;
}
for(j=0,i=at;i!=-1;i=pre[i])
ans[j++]=i+1;
for(i=j-1;i>=0;i--){
printf("%d",ans[i]);
if(i)printf(" ");
}
printf("\n%d\n",maxi);
return 0;
}
提高T4 砝码称重
用了完全背包，但是数据很弱，好像没有必要。
可以暴力枚举。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
using namespace std;
int f[1005]={0},n,v[6],ans=0;
void packX(int vv){//二进制枚举版本
int p=1,vi=vv,j;
while(n>=p){
for(j=1000;j>=vi;j--)
f[j]=max(f[j],f[j-vi]);
n-=p,p<<=1,vi<<=1;
}
if(n){
for(vi=n*vv,j=1000;j>=vi;j--)
f[j]=max(f[j],f[j-vi]);
}
}
int main(){
v[0]=1,v[1]=2,v[2]=3,v[3]=5,v[4]=10,v[5]=20;
f[0]=1;
for(int i=0;i<6;i++){
scanf("%d",&n);
if(n)packX(v[i]);
}
for(int i=1;i<=1000;i++)
ans+=f[i];
printf("Total=%d\n",ans);
return 0;
}
NOIP1997
普及T1 棋盘
自己推一下就行了。
长方形（含正方形）个数为
正方形个数为
1 |
|
普及T2 三角形
暴力枚举即可。
用了全排列。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;
int ans=0,p,rec[20],now[20]={1,2,3,4,5,6,7,8,9};
void cmp(){
if(!ans||memcmp(now,rec,sizeof(int)*9)<0)
memcpy(rec,now,sizeof(rec));
ans++;
}
int ok(){
return ((now[0]<now[5]&&now[5]<now[8])
&&(now[1]<now[3]&&now[6]<now[7]&&now[2]<now[4])
&&(now[0]+now[1]+now[3]+now[5]==p)
&&(now[6]+now[7]+now[8]+now[5]==p)
&&(now[0]+now[2]+now[4]+now[8]==p));
}
int main(){
scanf("%d",&p);
do{
if(ok())cmp();
}while(next_permutation(now,now+9));
if(!ans){
printf("NO\n");
return 0;
}
printf("%d\n",ans);
printf("%d\n%d %d\n%d %d\n%d %d %d %d\n",rec[0],
rec[1],rec[2],rec[3],rec[4],rec[5],rec[6],
rec[7],rec[8]);
return 0;
}
普及T3 街道
就是非常正常的DP。
递推式
之后再用一个简单的高精度就可以了。
1 |
|
提高T1 棋盘问题2（待考察？）
本题我只想出来了一种比较简单的搜索方法。。。
实际上原题数据很小，基本上各种搜索方法都可以过，但是当$N = 10$的时候就很难卡过去了。。。
1 |
|
NOIP1998
普及T1 寻找三位数
很简单的枚举。
只要从101枚举到333即可，然后记录每一位。
可以采用特殊策略优化，比如当前数字必须不是5的倍数。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
using namespace std;
char k[10];
int main(){
int a,b,c,d,fl,i;
for(a=101;a<=333;a++){
if(a%5==0)continue;
memset(k,0,sizeof(k));
fl=1,b=a,c=a*2,d=a*3;
k[b%10]++,k[c%10]++,k[d%10]++;
k[(b/10)%10]++,k[(c/10)%10]++,k[(d/10)%10]++;
k[b/100]++,k[c/100]++,k[d/100]++;
for(i=1;i<=9;i++)
if(k[i]!=1)
fl=0;
if(fl)printf("%d %d %d\n",b,c,d);
}
return 0;
}
普及T2 阶乘之和
高精度乘法+加法水过。1
2
普及T3 幂次方
递归计算即可。1
2
提高T1 火车站
设第二站上的人数是$p$，则：容易看出每一站上下车的人都等于$fib[i]a+fib[j]p$，其中$i$和$j$为相邻正整数。
那么只需要算出最终车上的人等于多少$a$加多少$p$，解出$p$，然后带入第$x$站的数据即可。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 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 a,n,m,x,fib[25],xs1[25],xs2[25];
void init(){
a=read(),n=read(),m=read(),x=read();
fib[0]=0,fib[1]=1;
for(int i=2;i<=24;i++)
fib[i]=fib[i-1]+fib[i-2];
}
void solve(){
xs1[1]=xs1[2]=1,xs2[1]=xs2[2]=0;
for(int i=3;i<n;i++)
xs1[i]=xs1[i-1]+fib[i-2]-fib[i-3],
xs2[i]=xs2[i-1]+fib[i-1]-fib[i-2];
printf("%d\n",xs1[x]*a+xs2[x]*(m-xs1[n-1]*a)/xs2[n-1]);
}
int main(){
init();
solve();
return 0;
}
提高T2 拼数
NOIP1999
普及T1 Cantor表
找规律，分奇偶讨论，最后$ \mathcal O(1)$计算。1
2
3
4
5
6
7
8
using namespace std;
int main(){
int n,i;scanf("%d",&n);
for(i=1;n>(i*i+i)/2;i++);
if(i%2==0)n=i*i+1-n;
printf("%d/%d\n",i+(i*i-i)/2+1-n,n-(i*i-i)/2);
}
普及T2 回文数
套用高精度加法模板即可。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
using namespace std;
typedef long long ll;
int n, s1[1005], s2[1005];
char s[1005];
void init(){
scanf("%d%s", &n, &s);
}
bool judge(int len){
for(int i = 1; i <= (len >> 1); ++i)
if(s1[i] != s1[len - i + 1]) return false;
return true;
}
void add(){
memset(s2, 0, sizeof(s2));
int x = 0;
s2[0] = s1[0];
for(int i = 1; i <= s1[0]; ++i){
x += s1[i] + s1[s1[0] - i + 1];
s2[i] = x % n;
x /= n;
}
if(x > 0) s2[++s2[0]] = x;
}
void solve(){
int len = strlen(s);
s1[0] = len;
for(int i = len - 1; i >= 0; --i){
if(isdigit(s[i])) s1[len - i] = s[i] - '0';
else s1[len - i] = s[i] - 'A' + 10;
}
int flag = 0;
for(int i = 0; i <= 30; ++i){
if(judge(s1[0])){
flag = 1;
printf("STEP=%d\n", i);
break;
}
add();
memcpy(s1, s2, sizeof(s2));
}
if(!flag) printf("Impossible!");
}
int main(){
init();
solve();
return 0;
}
提高T1 导弹拦截
先求最长不上升子序列，再求最长上升子序列。
（Dilworth定理，最长链和最长反链）
或者因为数据小，贪心的做法也能接受。
所以我无聊的写了三个版本：
$O(nlogn)$动态规划
1 |
|
$O(n^2)$动态规划
1 |
|
$O(n^2)$贪心
1 |
|
普及/提高T3 旅行家的预算
尽量选最便宜的，如果油满了就换次便宜的，这样递归（循环下去）。最后油全满了就No solution。
这里使用了优先队列来取最优值。只是懒得手写堆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
using namespace std;
typedef double db;
typedef struct{
int id;db count,dis,pri;
}Pp;
bool operator<(Pp a,Pp b){return a.pri>b.pri;}
Pp dat[105];int n;
db ans=0,C,D,per;
priority_queue<Pp> pq;
void solve(){
pq.push(dat[0]);
int i,j,k;
Pp tmp;
for(i=1;i<=n;i++){
db need=(dat[i].dis-dat[i-1].dis)/per,mini;
for(;!pq.empty();){
tmp=pq.top();
for(mini=need,j=tmp.id;j<i;j++)
mini=min(C-dat[j].count,mini);
for(j=tmp.id;j<i;j++)
dat[j].count+=mini;
ans+=mini*tmp.pri;
if(mini<need)
need-=mini,pq.pop();
else break;
}
if(pq.empty()){ans=-1;return ;}
pq.push(dat[i]);
}
}
int main(){
int i,j;
scanf("%lf%lf%lf%lf%d",&D,&C,&per,&dat[0].pri,&n);
for(i=1;i<=n;i++)
scanf("%lf%lf",&dat[i].dis,&dat[i].pri);
dat[0].dis=0;
for(n++,i=0;i<=n;i++)
dat[i].count=0,dat[i].id=i;
dat[n].dis=D;
solve();
if(ans<0)printf("No Solution\n");
else printf("%.2lf\n",ans);
return 0;
}