2019.10.3:蔡是原罪.所以蒟蒻决定从(1997)年开始刷每年的普及组和提高组的题.普及组应该都会刚完,提高组有些题选择性放弃.
2019.10.9:很抱歉,我又决定咕咕咕了,因为我发现以前的题太难了!!!!!!!!!!!!!!!!
2019.10.27:蒟蒻在考完鸽王的模拟赛DAY1之后痛定思痛,决定继续来填这个坑!!!!!!!!
(1997)普及组/提高组:
棋盘问题1
题意:设有一个(N imes M)方格的棋盘((1≤N≤100,1≤M≤100)),求出该棋盘中包含有多少个正方形、多少个长方形（不包括正方形）.
分析:直接推式子.正方形:长和宽相等,直接枚举边长即可,(sum_{i=1}^{min(n,m)}(n-i+1)(m-i+1)).矩形(包括正方形):长和宽可以不等,要分别枚举,(sum_{i=1}^nsum_{j=1}^m(n-i+1)(m-i+1)=sum_{i=1}^n(n-i+1)sum_{j=1}^m(m-i+1)),然后运用等差数列求和公式即可得(frac{n(n+1)}{2}frac{m(m+1)}{2}=(n+1)(m+1)nm/4.)
长方形数量即为两式相减.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
int n,m,ans1,ans2;
int main(){
n=read();m=read();if(n>m)swap(n,m);
for(int i=1;i<=n;++i)
ans1+=(n-i+1)*(m-i+1);
ans2=(n+1)*(m+1)*n*m/4;
printf("%d %d
",ans1,ans2-ans1);
return 0;
}
棋盘问题(2)
题意:在(N imes N)的棋盘上((1≤N≤5))，填入(1,2,…,N^2)共(N^2)个数，使得任意两个相邻的数之和为素数.如有多种解，则输出第一行、第一列之和为最小的排列方案；若无解，则输出“NO”.
直接爆搜的话,因为要保证第一行、第一列之和为最小的排列方案,所以(n=5)会超时,所以就(dfs)的同时记录了第一行第一列上的值,如果已经超过了当前的最小值,直接(return),一个小剪枝即可.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=15;
int n,Ans=1e9,a[N][N],BJ[N*N],ans[N][N];
int prime[N*N],v[N*N],bj[N*N];
inline void get_prime(){
int m=0;
for(int i=2;i<=200;++i){
if(!v[i]){
v[i]=i;BJ[i]=1;
prime[++m]=i;
}
for(int j=1;j<=m;++j){
if(prime[j]*i>200||prime[j]>v[i])break;
v[prime[j]*i]=prime[j];
}
}
}
inline bool pd(int num,int x,int y){
if(bj[num])return 0;
if(y>=2&&!BJ[a[x][y-1]+num])return 0;
if(x>=2&&!BJ[a[x-1][y]+num])return 0;
return 1;
}
inline void check(){
int cnt=0;
for(int i=1;i<=n;++i)cnt+=a[i][1];
for(int j=2;j<=n;++j)cnt+=a[1][j];
if(cnt>=Ans)return;Ans=cnt;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
ans[i][j]=a[i][j];
}
inline void dfs(int x,int y,int now){
if(now>=Ans)return;
if(y>n){
if(x==n){check();return;}
else dfs(x+1,1,now);
}
else{
for(int i=2;i<=n*n;++i){
if(pd(i,x,y)){
bj[i]=1;a[x][y]=i;
dfs(x,y+1,x==1||y==1?now+i:now);
bj[i]=0;
}
}
}
}
int main(){
get_prime();n=read();
if(n==1){puts("NO");return 0;}
a[1][1]=1;bj[1]=1;dfs(1,2,1);
if(Ans==1e9)puts("NO");
else{
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
printf("%d ",ans[i][j]);
}
printf("
");
}
}
return 0;
}
斐波那契数列（升级版）
题意:请你求出第n个斐波那契数列的数mod(2^{31})之后的值.并把它分解质因数.
分析:就直接根据题意分两步来做即可.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
ll mod=1<<31,f[50];
int p[50],c[50];
int main(){
int n=read();f[1]=1;f[2]=1;
if(n==1||n==2){
printf("%d=%d
",n,n);
return 0;
}
for(int i=3;i<=n;++i)f[i]=(f[i-2]+f[i-1])%mod;
ll m=f[n];int sum=0;
for(int i=2;i*i<=m;++i){
if(m%i==0){
p[++sum]=i;
while(m%i==0)++c[sum],m/=i;
}
}
if(m>1)p[++sum]=m,c[sum]=1;
printf("%lld=",f[n]);
for(int i=1;i<=sum;++i){
if(i>=2)printf("*");
printf("%d",p[i]);
for(int j=2;j<=c[i];++j){
printf("*%d",p[i]);
}
}
puts("");
return 0;
}
棋盘问题（2）【加强】
题意:在(N imes N)的棋盘上((1≤N≤10))，填入(1,2,…,N^2)共(N^2)个数，使得任意两个相邻的数之和为素数.
分析:预处理出(a[i][j])表示加上i之后是质数的第j个数,(b[i][j][k])表示加上i且加上j之后是质数的第k个数,其实就是为了在搜索枚举每个位置填什么数字的时候能够快一点,没必要1到(n^2)的枚举.
因为题目要保证第一行第一列的和最下,所以先搜索第一行,然后搜索第二列,再搜索剩下的格子.
然后发现(n=7)时方案不合法,(n=9)超时,打个表算了.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
int n,jz[15][15],bj[105];
int v[205],prime[105],a[105][105],b[105][105][50];
inline void prework(){
int m=0,max1=n*n,max2=max1*2;
for(int i=2;i<=max2;++i){
if(!v[i]){
v[i]=i;
prime[++m]=i;
}
for(int j=1;j<=m;++j){
if(prime[j]>v[i]||prime[j]*i>max2)break;
v[i*prime[j]]=prime[j];
}
}
for(int i=1;i<max1;++i)
for(int j=i+1;j<=max1;++j)
if(v[i+j]==i+j){
a[i][++a[i][0]]=j;
a[j][++a[j][0]]=i;
}
for(int i=1;i<max1;++i)
for(int j=i+1;j<=max1;++j)
for(int k=1;k<=a[i][0];++k)
if(v[a[i][k]+j]==a[i][k]+j){
b[i][j][++b[i][j][0]]=a[i][k];
b[j][i][++b[j][i][0]]=a[i][k];
}
}
inline void dfs(int now1,int now2){
if(now2>n){
if(now1==n){
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j)
printf("%d ",jz[i][j]);
printf("
");
}
exit(0);
}
else dfs(now1+1,2);
}
int x=jz[now1-1][now2],y=jz[now1][now2-1];
for(int i=1;i<=b[x][y][0];++i){
if(bj[b[x][y][i]])continue;
jz[now1][now2]=b[x][y][i];
bj[b[x][y][i]]=1;
dfs(now1,now2+1);
bj[b[x][y][i]]=0;
}
}
inline void dfs_lie(int now){
if(now>n){dfs(2,2);return;}
int last=jz[now-1][1];
for(int i=1;i<=a[last][0];++i){
if(bj[a[last][i]])continue;
jz[now][1]=a[last][i];
bj[a[last][i]]=1;
dfs_lie(now+1);
bj[a[last][i]]=0;
}
}
inline void dfs_hang(int now){
if(now>n){dfs_lie(2);return;}
int last=jz[1][now-1];
for(int i=1;i<=a[last][0];++i){
if(bj[a[last][i]])continue;
jz[1][now]=a[last][i];
bj[a[last][i]]=1;
dfs_hang(now+1);
bj[a[last][i]]=0;
}
}
int main(){
scanf("%d",&n);prework();jz[1][1]=1;bj[1]=1;
if(n==1){puts("NO");return 0;}
if(n==7){
printf("1 2 3 4 7 6 5
");
printf("12 17 14 15 16 25 18
");
printf("11 20 27 46 37 36 35
");
printf("8 33 40 43 30 23 38
");
printf("9 28 19 24 29 44 45
");
printf("10 31 42 47 32 39 34
");
printf("13 48 41 26 21 22 49
");
return 0;
}
if(n==9){
printf("1 2 3 4 7 6 5 8 9
");
printf("10 21 80 69 40 73 78 71 32
");
printf("13 76 51 62 27 34 19 60 77
");
printf("16 25 58 45 26 75 64 67 72
");
printf("15 28 39 68 35 38 63 46 37
");
printf("14 33 74 29 54 59 50 81 22
");
printf("17 20 53 18 49 24 47 56 57
");
printf("12 41 48 79 30 43 36 23 44
");
printf("11 42 55 52 31 70 61 66 65
");
return 0;
}
dfs_hang(2);puts("NO");
return 0;
}
(1998)普及组:
三连击
题意:将(1,2, cdots ,9)共(9)个数分成(3)组，分别组成(3)个三位数，且使这(3)个三位数构成(1:2:3)的比例，试求出所有满足条件的(3)个三位数.
分析:直接枚举第一个数的每一位,然后表示出第二,三个数,最后(check)一下是否合法即可.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
int bj[10];
inline bool check(int x,int y,int z){
memset(bj,0,sizeof(bj));
++bj[x%10];++bj[x/100];++bj[(x/10)%10];
++bj[y%10];++bj[y/100];++bj[(y/10)%10];
++bj[z%10];++bj[z/100];++bj[(z/10)%10];
for(int i=1;i<=9;++i)
if(bj[i]!=1)return 0;
return 1;
}
int main(){
for(int i=1;i<=9;++i)
for(int j=1;j<=9;++j)
for(int k=1;k<=9;++k){
int s1=i*100+j*10+k,s2=2*s1,s3=3*s1;
if(s3>999)continue;
if(check(s1,s2,s3))printf("%d %d %d
",s1,s2,s3);
}
return 0;
}
阶乘之和
题意:用高精度计算出(S=1!+2!+3!+…+n! (n≤50)).其中“!”表示阶乘，例如：(5!=5 imes 4 imes 3 imes 2 imes 1).
分析:因为不喜欢高精,也不会高精,就直接(kuai)的以前写的.
#include<bits/stdc++.h>
using namespace std;
int len=1,t[10001],ans[10001],anslen,n;
void jiecheng(int v){ //定义函数计算n的阶乘；
for(int i=1;i<=len;i++){
t[i]=t[i]*v; //每个位数都乘v；
}
int i=1;
while(t[i]>9||i<len){ //判断是否需要进位；
t[i+1]=t[i+1]+t[i]/10; //进位；
t[i]=t[i]%10; //只保留个位数；
i++; //继续对下一位进行处理；
}
len=i;
}
void jia(){
for(int i=1;i<=len;i++){
ans[i]=ans[i]+t[i]; //对每一位都相加；
if(ans[i]>9){ //当满足进位条件；
ans[i+1]=ans[i+1]+ans[i]/10; //进位；
ans[i]=ans[i]%10; //只保留个位；
anslen=max(anslen,i+1);
}
anslen=max(anslen,i); //判断当前数的位数，避免了多余的计算；
}
}
int main(){
scanf("%d",&n);
t[1]=1;
for(int i=1;i<=n;i++){
jiecheng(i),jia();
}
for(int i=anslen;i>=1;i--){
printf("%d",ans[i]);
}
return 0;
}
幂次方
题意略.
分析:一道分治好题,为什么难度才普及(-),挺难的啊.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
int Base[20];
inline void solve(int x){
int m;
for(int i=0;i<=15;++i){
if(Base[i]>x){
m=i-1;
break;
}
}
if(m==0)printf("2(0)");
if(m==1)printf("2");
if(m>=2){
printf("2(");
solve(m);
printf(")");
}
if(x-Base[m]>0){
printf("+");
solve(x-Base[m]);
}
}
int main(){
Base[0]=1;for(int i=1;i<=15;++i)Base[i]=Base[i-1]*2;
int n=read();solve(n);puts("");
return 0;
}
1998提高组:
车站
题意:火车从始发站（称为第(1)站）开出，在始发站上车的人数为(a)，然后到达第(2)站，在第(2)站有人上、下车，但上、下车的人数相同，因此在第(2)站开出时（即在到达第(3)站之前）车上的人数保持为(a)人。从第(3)站起（包括第(3)站）上、下车的人数有一定规律：上车的人数都是前两站上车人数之和，而下车人数等于上一站上车人数，一直到终点站的前一站（第(n-1)站），都满足此规律。现给出的条件是：共有(N)个车站，始发站上车的人数为(a)，最后一站下车的人数是(m)（全部下车）。试问(x)站开出时车上的人数是多少？(a(≤20))，(n(≤20))，(m(≤2000))，和(x(≤20)).
分析:这道题我推了一个小时的式子,我真的太弱了,而且还是手列表格.
设第一,二站上车人数为x人:
[ egin{matrix}
num & 1 & 2 & 3 & 4 & 5 & 6 & 7\
up & a & x & a+x & a+2x & 2a+3x & 3a+5x & 5a+8x\
down & 0 & x & x & a+x & a+2x & 2a+3x & 3a+5x\
end{matrix}
]
然后第n站下车的人数,就是第n-1站开出时车上的人数,第n站是没有人上车的.然后发现这一站下车的人数可以一一和上一站上车的人数抵消,所以第(n-1)站开出时车上的人数为 第一站上车人数+第(n-1)站上车人数-第二站下车人数 .所以有式子(f([(n-1)-2]+1)a+(f[(n-1)-1]-1)x=m)
解方程解出(x)之后,第p站开出时车上的人数,还是根据上式(ans=f([p-2]+1)a+(f[p-1]-1)x).
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
ll f[20];
int main(){
int a=read(),n=read(),m=read(),x=read();
f[1]=1;f[2]=1;for(int i=3;i<=18;++i)f[i]=f[i-2]+f[i-1];
int up=(m-(f[n-3]+1)*a)/(f[n-2]-1);
printf("%lld
",(f[x-2]+1)*a+(f[x-1]-1)*up);
return 0;
}
拼数
题意:设有(n)个正整数((n≤20))，将它们联接成一排，组成一个最大的多位整数
分析:就利用(string)可以直接相加,并且直接比较大小的性质.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
string s[20];
int main(){
int n;cin>>n;
for(int i=1;i<=n;++i)cin>>s[i];
for(int i=1;i<n;++i)
for(int j=i+1;j<=n;++j)
if(s[i]+s[j]<s[j]+s[i])swap(s[i],s[j]);
for(int i=1;i<=n;++i)cout<<s[i];cout<<endl;
return 0;
}
进制位
题意略.
分析:数论难,字符串细节多(->)这道题好难啊.
仔细观察一下样例,就会发现,进制=字母个数=(n-1),第二问就这么解决了.然后再仔细观察一下样例,就会发现,对于每一个字母,它那一行上两位数的个数就是它的值(这个值还等于字母总个数-1-该字母在两位数的个位上出现的次数).就这样判断得出答案即可.
细节问题我写进注释里面.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
string s;char order[10];
int a[10],bj[10];
map<string,int>Map;
map<char,int>b;
int main(){
int n;cin>>n;cin>>s;
for(int i=1;i<n;++i){
cin>>s;
order[i]=s[0];//题目最后要按照出现顺序输出,就记录一下
}//把第一行读掉,没什么用
for(int i=1;i<n;++i){
cin>>s;//把每一行的第一列读掉,没什么用
Map.clear();//清空map
for(int j=1;j<n;++j){
cin>>s;
if(Map[s]){
puts("ERROR!");
return 0;
}Map[s]=1;
//同一行上相同字符串只能出现一次,否则无解,亲测这里会有一个点
if(s.size()==2){
++a[i];
++b[s[1]];
}
//对于二位数,a[i]表示第i个字母所对应的行上二位数的个数
//b数组记录字母在二位数的各位出现的次数
}
}
for(int i=1;i<n;++i)++bj[a[i]];
for(int i=0;i<n-1;++i){
if(bj[i]!=1){
puts("ERROR!");
return 0;
}
}//0到n-2,每个数都要有一个,否则无解
for(int i=1;i<n;++i){
if(a[i]!=n-2-b[order[i]]){
puts("ERROR!");
return 0;
}
}//这个判断亲测会有一个点
for(int i=1;i<n;++i)printf("%c=%d ",order[i],a[i]);
printf("
%d
",n-1);
return 0;
}
(1999)普及组:
Cantor表
题意:现代数学的著名证明之一是Georg Cantor证明了有理数是可枚举的。他是用下面这一张表来证明这一命题的：
(1/1) , (1/2) , (1/3) , (1/4), (1/5), …
(2/1), (2/2) , (2/3), (2/4), …
(3/1) , (3/2), (3/3), …
(4/1), (4/2), …
(5/1), …
…
我们以(Z)字形给上表的每一项编号。第一项是(1/1)，然后是(1/2)，(2/1)，(3/1)，(2/2)，…求表的第(N(N<=10004000))项.
分析:又是一道普及(-),推了一个小时.主要就是各种分类讨论吧.也不好解释.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
int main(){
int n=read(),i;
for(i=1;i<=5000;++i){
if(i*(i+1)/2>n)break;
}
if(i*(i-1)/2==n){
if(i&1)printf("%d/1
",i-1);
else printf("1/%d
",i-1);
return 0;
}
if(i&1){
n-=i*(i-1)/2;
printf("%d/%d
",i+1-n,n);
}
else{
n-=i*(i-1)/2;
printf("%d/%d
",n,i+1-n);
}
return 0;
}
回文数
题意:若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。例如：给定一个十进制数(56)，将(56)加(65)（即把(56)从右向左读），得到(121)是一个回文数。
又如：对于十进制数(87)：
STEP1：(87)+(78) = (165)
STEP2：(165)+(561) = (726)
STEP3：(726)+(627) = (1353)
STEP4：(1353)+(3531) = (4884)
在这里的一步是指进行了一次(N)进制的加法，上例最少用了(4)步得到回文数(4884)。
写一个程序，给定一个(N)((2 le N le 10,N=16))进制数(M)((100)位之内)，求最少经过几步可以得到回文数。如果在(30)步以内（包含(30)步）不可能得到回文数，则输出Impossible!.
分析:又是一道字符串,又搞了一个小时,普及组的题都这么难的么;没有思维难度啊,就每一步按照题意来模拟就行,每得到一个数字就去(check)是否回文即可.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
char s[100005],s1[1000005];
inline bool check(){
int len=strlen(s+1);
for(int i=1;i<=len/2;++i){
if(s[i]!=s[len+1-i])return 0;
}
return 1;
}
char zm[20]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
int main(){
int n,step=0;
scanf("%d%s",&n,s+1);
while(1){
if(check()){
printf("STEP=%d
",step);
return 0;
}
if(step>=30)break;
int len=strlen(s+1),bj=0;
for(int i=1;i<=len;++i){
int now=s[i]-(s[i]>=65?'A'-10:'0')+s[len+1-i]-(s[len+1-i]>=65?'A'-10:'0')+bj;
bj=0;
if(now>=n){now-=n;bj=1;}
s1[len-i+1]=zm[now];
}
if(bj){
s1[0]='1';
for(int i=1;i<=len+1;++i)s[i]=s1[i-1];
}
else for(int i=1;i<=len;++i)s[i]=s1[i];
++step;
}
puts("Impossible!");
return 0;
}
导弹拦截
题意:某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹.输入导弹依次飞来的高度（雷达给出的高度数据是$ le 50000$的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统.
分析:绿题反而更好写???两问毫不相干,分来来做,对于第一问"这套系统最多能拦截多少导弹",设(f[i])表示一套系统打下的第i枚导弹的高度,那么扫描的时候能打就打,不能打就去前面找到第一个比当前导弹低的替换掉.
第二问也是能打就打,不能打就新建一个系统.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
const int N=100005;
int a[N],f[N];
int main(){
int high,n=0,now;
while(scanf("%d",&high)!=EOF)a[++n]=high;
f[1]=a[1];now=1;
for(int i=2;i<=n;++i){
if(f[now]>=a[i])f[++now]=a[i];
else{
for(int j=1;j<=now;++j)
if(f[j]<a[i]){f[j]=a[i];break;}
}
}
printf("%d
",now);
f[1]=a[1];now=1;
for(int i=2;i<=n;++i){
if(f[now]<a[i])f[++now]=a[i];
else{
for(int j=1;j<=now;++j)
if(f[j]>=a[i]){f[j]=a[i];break;}
}
}
printf("%d
",now);
return 0;
}
(1999)提高组:
旅行家的预算
题意:一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）.给定两个城市之间的距离(D1)、汽车油箱的容量(C)（以升为单位）、每升汽油能行驶的距离(D2)、出发点每升汽油价格(P)和沿途油站数(N)（(N)可以为零），油站(i)离出发点的距离(Di)、每升汽油价格(Pi)（(i=1,2,…,N)）.计算结果四舍五入至小数点后两位.如果无法到达目的地，则输出("No) (Solution".)
分析:最不喜欢做贪心+模拟的题了,细节超级多,容许我留个坑.
邮票面值设计
题意:给定一个信封，最多只允许粘贴(N)张邮票，计算在给定(K)（(N+K≤15)）种邮票的情况下（假定所有的邮票数量都足够），如何设计邮票的面值，能得到最大值(MAX)，使在(1)至(MAX)之间的每一个邮资值都能得到.例如，(N=3)，(K=2)，如果面值分别为(1)分、(4)分，则在(1)分～(6)分之间的每一个邮资值都能得到（当然还有(8)分、(9)分和(12)分）；如果面值分别为(1)分、(3)分，则在(1)分～(7)分之间的每一个邮资值都能得到.可以验证当(N=3)，(K=2)时，(7)分就是可以得到的连续的邮资最大值，所以(MAX=7)，面值分别为(1)分、(3)分.
分析:直接(dfs)枚举选哪(k)种面值的邮票,每搜索到一个值,就(dp)(这应该算是个多重背包吧)计算当前所能够产生的最大值,以便于搜索数量的减少.
最近做了好多道先(dfs)穷举状态,然后(dp)计算该状态下的最优解的题.本题还在于(dp)的值有利于我们搜索剪枝.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
int n,k,Ans,ans[20],num[20],f[100005];
inline int dp(int x){
for(int i=1;i<=num[x]*n;++i)f[i]=1e9;f[0]=0;
for(int i=1;i<=x;++i)
for(int j=num[i];j<=num[x]*n;++j)
f[j]=min(f[j],f[j-num[i]]+1);
for(int i=1;i<=num[x]*n;++i)if(f[i]>n)return i-1;
return num[x]*n;
}
inline void dfs(int now,int maxn){
if(now>k){
if(maxn>Ans){
Ans=maxn;
for(int i=1;i<=k;++i)ans[i]=num[i];
}
return;
}
for(int i=num[now-1]+1;i<=maxn+1;++i){//这个枚举的上下界都懂吧
num[now]=i;dfs(now+1,dp(now));
}
}
int main(){
n=read();k=read();dfs(1,0);
for(int i=1;i<=k;++i)printf("%d ",ans[i]);
printf("
MAX=%d
",Ans);
return 0;
}
(2000)普及组:
题意:税收与补贴问题
这道题不太想讲,因为看懂题意就搞了很久,然后严重怀疑第四个数据点是有问题的,搞得我额外为这个点写了几十行代码,很不爽.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
int a[10000],b[10000],c[10000],d[10000];
int main(){
int n=read(),m=0,pos=0,ans=1e9;
while(1){
int x=read(),y=read();if(x==-1&&y==-1)break;
a[++m]=x;b[m]=y;
}
int k=read();
while(1){
if(b[m]<=k)break;
a[m+1]=a[m]+1;b[m+1]=b[m]-k;++m;
}
for(int i=1;i<=m;++i)if(a[i]==n)pos=i;
if(!pos){//处理第四个点
int xl=abs(b[m]-b[1])/abs(a[m]-a[1]);
int tot=1;c[1]=a[1];d[1]=b[1];
while(1){
if(d[tot]<=xl)break;
c[tot+1]=c[tot]+1;d[tot+1]=d[tot]-xl;++tot;
}
for(int i=1;i<=tot;++i)if(c[i]==n)pos=i;
for(int i=-1000;i<=1000;++i){
int ppx=(c[pos]-c[1]+i)*d[pos],bj=1;
for(int j=1;j<=tot;++j){
if(j==pos)continue;
if((c[j]-c[1]+i)*d[j]>ppx){
bj=0;break;
}
}
if(bj){
if(abs(i)<abs(ans))ans=i;
}
}
if(ans==1e9)puts("NO SOLUTION");
else printf("%d
",ans);
return 0;
}
for(int i=-1000;i<=1000;++i){
int ppx=(a[pos]-a[1]+i)*b[pos],bj=1;
for(int j=1;j<=m;++j){
if(j==pos)continue;
if((a[j]-a[1]+i)*b[j]>ppx){
bj=0;break;
}
}
if(bj){
if(abs(i)<abs(ans))ans=i;
}
}
if(ans==1e9)puts("NO SOLUTION");
else printf("%d
",ans);
return 0;
}
计算器的改良
字符串+大模拟=不想做.
(2000)提高组
方格取数
题意:(n*n)的棋盘,有些点有权值,两次从左上角走到右下角,一个点的权值经过后就变成零了,求最大得分.
直接设(f[i][j][k][l])暴力转移即可.
费用流也可以做.时间复杂度都差不多,但是代码量就........
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=10;
int val[N][N],f[N][N][N][N];
int main(){
int n=read();
while(1){
int x=read(),y=read(),z=read();
if(!x&&!y&&!z)break;val[x][y]=z;
}
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
for(int k=1;k<=n;++k)
for(int l=1;l<=n;++l){
f[i][j][k][l]=max(f[i-1][j][k-1][l],max(f[i-1][j][k][l-1],max(f[i][j-1][k-1][l],f[i][j-1][k][l-1])))+val[i][j]+val[k][l];
if(i==k&&j==l)f[i][j][k][l]-=val[i][j];
}
printf("%d
",f[n][n][n][n]);
return 0;
}
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=100005;
int n,s,t,max_flow,ans,val[10][10];
int dis[N],visit[N],incf[N],pre[N];
int tot,head[N],nxt[N],to[N],limit[N],w[N];
inline void add(int a,int b,int c,int d){
nxt[++tot]=head[a];head[a]=tot;to[tot]=b;limit[tot]=c;w[tot]=d;
nxt[++tot]=head[b];head[b]=tot;to[tot]=a;limit[tot]=0;w[tot]=-d;
}
inline bool spfa(){
for(int i=1;i<=2*n*n;++i)dis[i]=-1e9,visit[i]=0;
queue<int>q;q.push(s);dis[s]=0;visit[s]=1;incf[s]=1e9;
while(q.size()){
int u=q.front();q.pop();visit[u]=0;
for(int i=head[u];i;i=nxt[i]){
if(!limit[i])continue;
int v=to[i];
if(dis[v]<dis[u]+w[i]){
dis[v]=dis[u]+w[i];
incf[v]=min(incf[u],limit[i]);
pre[v]=i;
if(!visit[v])visit[v]=1,q.push(v);
}
}
}
if(dis[t]==-1e9)return 0;
return 1;
}
inline void update(){
int x=t;
while(x!=s){
int i=pre[x];
limit[i]-=incf[t];
limit[i^1]+=incf[t];
x=to[i^1];
}
max_flow+=incf[t];
ans+=dis[t]*incf[t];
}
int main(){
n=read();tot=1;s=1;t=2*n*n;
while(1){
int x=read(),y=read(),z=read();
if(!x&&!y&&!z)break;val[x][y]=z;
}
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
int num=(i-1)*n+j;
add(num,num+n*n,1,val[i][j]);
add(num,num+n*n,1,0);
if(j+1<=n)add(num+n*n,num+1,2,0);
if(i+1<=n)add(num+n*n,num+n,2,0);
}
}
while(spfa())update();
printf("%d
",ans);
return 0;
}
乘积最大
题意略.
(DP)很好想,设(f[i][j])表示前i个数分成j段的最大乘积,则(f[i][j]=max(f[k][j-1]+sum[k+1][j])).初始化(f[i][0]=1,f[i][1]=sum[1][i]),目标(f[n][m+1]).
(long) (long)有(60)分,(int128)有(80)分,高精(100)分,懒得写了.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
const int N=50;
int n,m;
__int128 sum[N][N],f[N][N];
char s[N];
inline void print(__int128 x){
if(!x)return;
if(x<0)putchar('-'),x=-x;
print(x/10);putchar(x%10+'0');
}
int main(){
scanf("%d%d%s",&n,&m,s+1);
for(int i=1;i<=n;++i)
for(int j=i;j<=n;++j)
for(int k=i;k<=j;++k)
sum[i][j]=(__int128)sum[i][j]*10+s[k]-'0';
for(int i=1;i<=n;++i)f[i][0]=1,f[i][1]=sum[1][i];
for(int i=1;i<=n;++i)
for(int j=1;j<=m+1;++j){
if(i<j)continue;
for(int k=1;k<i;++k){
if(k>=j-1)f[i][j]=max(f[i][j],f[k][j-1]*sum[k+1][i]);
}
}
print(f[n][m+1]);puts("");
return 0;
}