「JoyOI」P1001 – 1099题解(44 / 99)by hzwer
只写简要题解，详见JoyOI官方题解
我会尽量给出简单直白的代码
「JoyOI1001」第K极值
排序，计算出m并判断其是不是质数
只需要循环到√m即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#include<cmath> #include<cstdio> #include<algorithm> using namespace std; int n,k,m; int a[10005]; bool isprime(int x) { if(x<=1)return false; for(int i=2;i<=sqrt(x);i++) if(x%i==0)return false; return true; } int main() { scanf("%d%d",&n,&k); for(int i=1;i<=n;i++)scanf("%d",&a[i]); sort(a+1,a+n+1); m=a[n-k+1]-a[k]; if(isprime(m))puts("YES"); else puts("NO"); printf("%d\n",m); return 0; } |
「JoyOI1002」NOIP2005谁拿了最多奖学金
模拟
|
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 |
#include<cmath> #include<cstdio> #include<algorithm> using namespace std; int n; char ch[105][20],cadre[2],west[2]; int score1,score2,art,tot; int ans,mx; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%s",ch[i]); scanf("%d%d%s%s%d",&score1,&score2,cadre,west,&art); int Money=0; if(score1>80&&art>=1)Money+=8000; if(score1>85&&score2>80)Money+=4000; if(score1>90)Money+=2000; if(score1>85&&west[0]=='Y')Money+=1000; if(score2>80&&cadre[0]=='Y')Money+=850; tot+=Money; if(Money>mx) mx=Money,ans=i; } printf("%s\n",ch[ans]); printf("%d\n%d\n",mx,tot); return 0; } |
「JoyOI1003」越野跑
如果是平地，来回要花2F时间，否则花U+D的时间
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include<cmath> #include<cstdio> #include<algorithm> using namespace std; int m,t,u,f,d; char ch[2]; int main() { scanf("%d%d%d%d%d",&m,&t,&u,&f,&d); for(int i=1;i<=t;i++) { scanf("%s",ch); if(ch[0]=='f') m-=2*f; else m-=(u+d); if(m<0) { printf("%d\n",i-1); return 0; } } return 0; } |
「JoyOI1004」滑雪
记忆化搜索，从每个点向更低点记忆化深搜
|
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 |
#include<cmath> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int r,c,ans; int h[105][105],f[105][105]; int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0}; int dfs(int x,int y) { if(x<1||y<1||x>r||y>c)return 0; if(f[x][y]!=-1)return f[x][y]; f[x][y]=1; for(int i=0;i<4;i++) { int tx=x+xx[i],ty=y+yy[i]; if(h[tx][ty]<h[x][y]) f[x][y]=max(f[x][y],dfs(tx,ty)+1); } return f[x][y]; } int main() { memset(f,-1,sizeof(f)); scanf("%d%d",&r,&c); for(int i=1;i<=r;i++) for(int j=1;j<=c;j++) scanf("%d",&h[i][j]); for(int i=1;i<=r;i++) for(int j=1;j<=c;j++) if(f[i][j]==-1) ans=max(ans,dfs(i,j)); printf("%d\n",ans); return 0; } |
「JoyOI1005」NOIP2005采药
01背包，f(i)表示花费i的时间能获得的最大价值
第二重时间倒序循环，保证一种草药只选一次
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
#include<cmath> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int T,n,ans; int f[1005],t[105],w[105]; int main() { scanf("%d%d",&T,&n); for(int i=1;i<=n;i++) scanf("%d%d",&t[i],&w[i]); for(int i=1;i<=n;i++) for(int j=T;j>=0;j--) if(j+t[i]<=T) f[j+t[i]]=max(f[j+t[i]],f[j]+w[i]); for(int i=0;i<=T;i++) ans=max(ans,f[i]); printf("%d\n",ans); return 0; } |
「JoyOI1006」NOIP2008ISBN号码
模拟
|
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 |
#include<cmath> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; char ch[15],ans; int num,cnt; int main() { scanf("%s",ch+1); for(int i=1;i<=11;i++) if(ch[i]!='-') { cnt++; num+=(ch[i]-'0')*cnt; num%=11; } if(num<10)ans=num+'0'; else ans='X'; if(ans==ch[13])puts("Right"); else { ch[13]=ans; printf("%s",ch+1); } return 0; } |
「JoyOI1007」NOIP2008排座椅
先统计划分某一行/列能减少多少说话的对数
贪心取最大的若干行/列
|
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<cmath> #include<cstdio> #include<vector> #include<algorithm> using namespace std; int m,n,K,L,D; struct data{ int pos,v; friend bool operator<(data a,data b){ if(a.v==b.v)return a.pos<b.pos; return a.v>b.v; } }r[1005],c[1005]; vector<int>ans1,ans2; int main() { scanf("%d%d%d%d%d",&m,&n,&K,&L,&D); for(int i=1;i<=m;i++) r[i].pos=i; for(int i=1;i<=n;i++) c[i].pos=i; for(int i=1;i<=D;i++) { int x,y,p,q; scanf("%d%d%d%d",&x,&y,&p,&q); if(x==p)c[min(q,y)].v++; else r[min(x,p)].v++; } sort(r+1,r+m+1); sort(c+1,c+n+1); for(int i=1;i<=K;i++) ans1.push_back(r[i].pos); for(int i=1;i<=L;i++) ans2.push_back(c[i].pos); sort(ans1.begin(),ans1.end()); sort(ans2.begin(),ans2.end()); for(int i=0;i<ans1.size();i++) printf("%d ",ans1[i]); puts(""); for(int i=0;i<ans2.size();i++) printf("%d ",ans2[i]); puts(""); return 0; } |
「JoyOI1008」NOIP2008传球游戏
用f(i,j)表示前i次传球，传给j的方案数
\[则f(i,j) => f(i+1,j+1)\]
\[f(i,j) => f(i+1,j-1)\]
\[边界f(0,1) =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 |
#include<cmath> #include<cstdio> #include<vector> #include<algorithm> using namespace std; int n,m; int f[35][35]; int g(int x) { if(x<1)return x+n; if(x>n)return x-n; return x; } int main() { scanf("%d%d",&n,&m); f[0][1]=1; for(int i=0;i<=m;i++) for(int j=1;j<=n;j++) { f[i+1][g(j+1)]+=f[i][j]; f[i+1][g(j-1)]+=f[i][j]; } printf("%d\n",f[m][1]); return 0; } |
「JoyOI1009」NOIP2008立体图（略）
「JoyOI1010」NOIP2008笨小猴
统计一下字母的出现次数，然后同1001
|
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 |
#include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<algorithm> using namespace std; int l,m; int cnt[30]; char ch[105]; bool isprime(int x) { if(x<=1)return false; for(int i=2;i<=sqrt(x);i++) if(x%i==0)return false; return true; } int main() { scanf("%s",ch+1); l=strlen(ch+1); for(int i=1;i<=l;i++) cnt[ch[i]-'a']++; sort(cnt,cnt+26); for(int i=0;i<=25;i++) if(cnt[i]) { m=cnt[25]-cnt[i]; break; } if(!isprime(m)) { m=0; puts("No Answer"); } else puts("Lucky Word"); printf("%d\n",m); return 0; } |
「JoyOI1011」NOIP2008传纸条
可以看成从（1，1）到（m，n）找两条不相交的路径
f(i,j,k)表示传到第i个人，第一条路径在第j行，第二条路径在第k行的最大价值
|
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 |
#include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<algorithm> using namespace std; int m,n; int a[55][55]; int f[105][55][55]; int main() { scanf("%d%d",&m,&n); for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) scanf("%d",&a[i][j]); f[1][1][1]=0; for(int i=1;i<=n+m;i++) for(int j=1;j<=m&&j<=i;j++) for(int k=1;k<=m&&k<=i;k++) if(j!=k||i==n+m) { f[i][j][k]=max(f[i][j][k],f[i-1][j][k]); f[i][j][k]=max(f[i][j][k],f[i-1][j-1][k-1]); f[i][j][k]=max(f[i][j][k],f[i-1][j-1][k]); f[i][j][k]=max(f[i][j][k],f[i-1][j][k-1]); f[i][j][k]+=a[j][i-j+1]+a[k][i-k+1]; } printf("%d\n",f[n+m][m][m]); return 0; } |
「JoyOI1012」NOIP2008火柴棒等式
枚举A，B验证
|
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 |
#include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<algorithm> using namespace std; int n,ans; int cnt[10]={6,2,5,5,4,5,6,3,7,6}; int get(int x) { if(x==0)return 6; int tot=0; while(x) { tot+=cnt[x%10]; x/=10; } return tot; } int main() { scanf("%d",&n); n-=4; for(int i=0;i<=1000;i++) for(int j=0;j<=1000;j++) if(get(i)+get(j)+get(i+j)==n) ans++; printf("%d\n",ans); return 0; } |
「JoyOI1013」找啊找啊找GF
用\(F(i,j)\)表示消费 i 金钱 j 点 rp 能泡到的最多妹子
做一个01背包
用\(G(i,j)\)表示最小的代价
|
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 |
#include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<algorithm> #define inf 1000000000 using namespace std; int ans,mn; int n,m,r; int rmb[105],rp[105],Time[105]; int f[105][105],g[105][105]; int main() { memset(g,127,sizeof(g)); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d%d",&rmb[i],&rp[i],&Time[i]); scanf("%d%d",&m,&r); g[0][0]=0; for(int i=0;i<n;i++) for(int j=m-rmb[i+1];j>=0;j--) for(int k=r-rp[i+1];k>=0;k--) if(g[j][k]<inf) { int p=j+rmb[i+1],q=k+rp[i+1]; if(f[j][k]+1>f[p][q]) { f[p][q]=f[j][k]+1; g[p][q]=g[j][k]+Time[i+1]; } if(f[j][k]+1==f[p][q]) g[p][q]=min(g[p][q],g[j][k]+Time[i+1]); if(f[p][q]>ans) ans=f[p][q],mn=g[p][q]; if(f[p][q]==ans) mn=min(mn,g[p][q]); } printf("%d\n",mn); return 0; } |
「JoyOI1014」乘法游戏
用dp(l,r)表示将 l 到 r 移动到只剩两张卡片的最小分数
枚举区间内最后一张取出来的牌，则
\[dp(l,r) = min\{dp(l,k)+dp(k,r)+a_l*a_k*a_r\}\]
记忆化搜索
|
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 |
#include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<algorithm> #define inf 1000000000 using namespace std; int n; int a[105],f[105][105]; int dp(int l,int r) { if(l+1==r)return 0; if(f[l][r]<inf)return f[l][r]; for(int k=l+1;k<=r-1;k++) f[l][r]=min(f[l][r],dp(l,k)+dp(k,r)+a[l]*a[k]*a[r]); return f[l][r]; } int main() { memset(f,127,sizeof(f)); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); printf("%d\n",dp(1,n)); return 0; } |
「JoyOI1015」公路乘车
\[F_i表示移动i公里的最小代价\]
\[则F_i=min\{f_{i-j}+m_j\}\]
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<algorithm> #define inf 1000000000 using namespace std; int n; int m[15],f[105]; int main() { memset(f,127,sizeof(f)); f[0]=0; for(int i=1;i<=10;i++) scanf("%d",&m[i]); scanf("%d",&n); for(int i=1;i<=10;i++) for(int j=0;j<=n;j++) if(f[j]<inf) f[j+i]=min(f[j+i],f[j]+m[i]); printf("%d\n",f[n]); return 0; } |
「JoyOI1016」NOIP2001装箱问题
最简单的01背包问题，f(i)表示能否得到 i 的体积
推荐阅读《背包九讲》
|
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 |
#include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<algorithm> #define inf 1000000000 using namespace std; int v,n; int a[35]; bool f[20005]; int main() { scanf("%d%d",&v,&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); f[0]=1; for(int i=1;i<=n;i++) for(int j=v-a[i];j>=0;j--) if(f[j])f[j+a[i]]=1; for(int i=v;i>=0;i--) if(f[i]) { printf("%d\n",v-i); break; } return 0; } |
「JoyOI1017」冗余关系
并查集，依次合并集合，输出有多少次合并是无效的
|
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 |
#include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<algorithm> #define inf 1000000000 using namespace std; int n,m,ans; int fa[1005]; int find(int x) { return x==fa[x]?x:fa[x]=find(fa[x]); } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=m;i++) { int u,v; scanf("%d%d",&u,&v); u=find(u);v=find(v); if(u==v)ans++; fa[u]=v; } printf("%d\n",ans); return 0; } |
「JoyOI1018」阶乘统计
答案可以直接用long long存下来，去掉0之后输出它的最后几位
|
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 |
#include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; int n,K,m; int a[25]; ll ans=1; int main() { scanf("%d%d",&n,&K); for(int i=1;i<=n;i++) ans*=i; while(ans%10==0)ans/=10; while(ans) { a[++m]=ans%10; ans/=10; } for(int i=min(m,K);i>=1;i--) printf("%d",a[i]); return 0; } |
「JoyOI1019」配对
将A数列从小到大排序，B数列从大到小排序，依次配对
|
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 |
#include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; int n,ans; int a[10005],b[10005]; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) scanf("%d",&b[i]); sort(a+1,a+n+1); sort(b+1,b+n+1,greater<int>()); for(int i=1;i<=n;i++) ans+=abs(a[i]-b[i]); printf("%d\n",ans); return 0; } |
「JoyOI1020」寻找质因数
对每个数字分解质因数
|
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 |
#include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; int n,mx,ans; int get(int x) { int ans=1; for(int i=2;i<=sqrt(x);i++) while(x%i==0) x/=i,ans=max(ans,i); ans=max(ans,x); return ans; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { int x;scanf("%d",&x); if(get(x)>mx) mx=get(x),ans=x; } printf("%d\n",ans); return 0; } |
「JoyOI1021」线段长度
将坐标排序后，计算每一条小线段对答案的贡献
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
#include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; int n; long long a[10005],ans; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+n+1); for(int i=1;i<n;i++) ans+=(a[i+1]-a[i])*i*(n-i); printf("%lld",ans*2); return 0; } |
「JoyOI1022」进制转换
从低位开始，用n除以该位的进制数，看结果是否为奇数，注意要开longlong
|
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 |
#include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; ll n; int p,ans[35]; int main() { scanf("%lld",&n); for(ll i=1;p<=32;i*=(-2),p++) if((n/i)&1) { ans[p]=1; n-=i; } while(!ans[p]&&p!=0)p--; for(int i=p;i>=0;i--) printf("%d",ans[i]); return 0; } |
「JoyOI1023」奶牛的锻炼
用f(i,j)表示第i天结束，疲劳值为j的最远跑步距离
则\(f(i,j)=f(i-1,j-1)+D_i\)
\(f(i,0)=max\{f(i-j,j)\}\)
|
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 |
#include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; int n,m; int d[2005],f[2005][505]; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&d[i]); for(int i=1;i<=n;i++) { f[i][0]=f[i-1][0]; for(int j=1;j<=m;j++) { f[i][j]=f[i-1][j-1]+d[i]; if(j<=i)f[i][0]=max(f[i][0],f[i-j][j]); } } printf("%d\n",f[n][0]); return 0; } |
「JoyOI1024」外星人的密码数字
根据第一行的字母表得到每个字母的权值
然后用\(O(n^2)\)的dp来求最长不降子序列
\(f_i\)表示以第i个字母结尾的最长不降子序列
\(f_i=max\{f_j\}+1\)(第j个字母权值不大于第i个字母)
|
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 |
#include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; int l,ans; int val[26],f[256]; char ch[256]; int main() { scanf("%s",ch+1); for(int i=1;i<=26;i++) val[ch[i]-'a']=i; while(scanf("%s",ch+1)!=EOF) { l=strlen(ch+1); ans=0; memset(f,0,sizeof(f)); for(int i=1;i<=l;i++) for(int j=0;j<i;j++) if(val[ch[i]-'a']>=val[ch[j]-'a']) { f[i]=max(f[j]+1,f[i]); ans=max(ans,f[i]); } printf("%d",ans); } return 0; } |
「JoyOI1025」单数？双数？
不明觉厉
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
#include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; int n; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { ll x; scanf("%lld",&x); if(x&1)puts("odd"); else puts("even"); } return 0; } |
「JoyOI1026」犁田机器人
由于地图小指令少，所以模拟即可
每次把要犁的地for一遍，打上标记，最后统计标记数量
复杂度\(O(XYL)\)
|
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 |
#include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; int X,Y,L,ans; bool mark[255][255]; int main() { scanf("%d%d%d",&X,&Y,&L); for(int i=1;i<=L;i++) { int x_1,y_1,x_2,y_2; scanf("%d%d%d%d",&x_1,&y_1,&x_2,&y_2); for(int j=x_1;j<=x_2;j++) for(int k=y_1;k<=y_2;k++) if(!mark[j][k]) { ans++; mark[j][k]=1; } } printf("%d\n",ans); return 0; } |
「JoyOI1027」木瓜地
从(1,1)开始搜索，每次走相邻的最大值，走过的格子赋值为-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 |
#include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; int a[45][45]; int r,c,ans; int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0}; void dfs(int x,int y) { ans+=a[x][y]; if(x==r&&y==c)return; a[x][y]=-1; int mxx=0,mxy=0; for(int d=0;d<4;d++) { int dx=x+xx[d],dy=y+yy[d]; if(dx<1||dy<1||dx>r||dy>c)continue; if(a[dx][dy]>a[mxx][mxy]) mxx=dx,mxy=dy; } dfs(mxx,mxy); } int main() { scanf("%d%d",&r,&c); for(int i=1;i<=r;i++) for(int j=1;j<=c;j++) scanf("%d",&a[i][j]); dfs(1,1); printf("%d\n",ans); return 0; } |
「JoyOI1028」Bessie的体重
同1016
|
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 |
#include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; int H,n; int s[505]; bool f[45005]; int main() { scanf("%d%d",&H,&n); for(int i=1;i<=n;i++) scanf("%d",&s[i]); f[0]=1; for(int i=1;i<=n;i++) for(int j=H;j>=s[i];j--) if(f[j-s[i]])f[j]=1; for(int i=H;i>=0;i--) if(f[i]) { printf("%d\n",i); return 0; } return 0; } |
「JoyOI1029」牛棚回声
枚举答案，正反模拟判断
|
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 |
#include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; char a[105],b[105]; bool check(char a[],char b[],int l) { int l2=strlen(b+1); for(int i=1;i<=l;i++) if(a[i]!=b[l2-l+i])return 0; return 1; } int main() { scanf("%s",a+1); scanf("%s",b+1); int l1=strlen(a+1),l2=strlen(b+1); for(int i=min(l1,l2);i>=1;i--) if(check(a,b,i)||check(b,a,i)) { printf("%d\n",i); return 0; } return 0; } |
「JoyOI1030」乳草的入侵
从起点开始bfs，注意坐标的方向
|
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 |
#include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; int n,m,Mx,My,ans; int head,tail=1,qx[10005],qy[10005]; int xx[8]={-1,-1,-1,0,0,1,1,1},yy[8]={1,-1,0,1,-1,1,-1,0}; int d[105][105]; char a[105][105]; void bfs() { qx[0]=Mx;qy[0]=My; d[Mx][My]=0; while(head!=tail) { int x=qx[head],y=qy[head];head++; ans=d[x][y]; for(int i=0;i<8;i++) { int dx=x+xx[i],dy=y+yy[i]; if(dx<1||dy<1||dx>m||dy>n||a[dx][dy]=='*'||d[dx][dy]!=-1) continue; d[dx][dy]=d[x][y]+1; qx[tail]=dx;qy[tail]=dy;tail++; } } } int main() { memset(d,-1,sizeof(d)); scanf("%d%d%d%d",&n,&m,&My,&Mx); for(int i=m;i>0;i--) scanf("%s",a[i]+1); bfs(); printf("%d\n",ans); return 0; } |
「JoyOI1031」热浪
求Ts到Te的最短路，随便选种算法写都可以
这里给出的是堆优化的dijkstra
|
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 |
#include<cmath> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #define pa pair<int,int> #define inf 1000000000 #define ll long long using namespace std; int T,C,Ts,Te; int dis[2505]; bool vis[2505]; vector<int>e[2505],c[2505]; priority_queue<pa,vector<pa>,greater<pa> >q; void dijkstra() { memset(dis,127/3,sizeof(dis)); q.push(make_pair(0,Ts));dis[Ts]=0; while(!q.empty()) { int now=q.top().second;q.pop(); if(vis[now])continue;vis[now]=1; for(int i=0;i<e[now].size();i++) if(dis[now]+c[now][i]<dis[e[now][i]]) { dis[e[now][i]]=dis[now]+c[now][i]; q.push(make_pair(dis[e[now][i]],e[now][i])); } } } int main() { scanf("%d%d%d%d",&T,&C,&Ts,&Te); for(int i=1;i<=C;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); e[u].push_back(v); e[v].push_back(u); c[u].push_back(w); c[v].push_back(w); } dijkstra(); printf("%d\n",dis[Te]); return 0; } |
「JoyOI1032」零花钱
小的面值能整除大面值，因此可以想到一个贪心的做法
先用尽量大的面值凑，最后选一个面值最小的，这样可以使浪费尽可能少
|
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 |
#include<cmath> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; int n,c,ans; struct data{ int v,b; friend bool operator<(data a,data b){ return a.v<b.v; } }a[25]; int main() { scanf("%d%d",&n,&c); for(int i=1;i<=n;i++) { scanf("%d%d",&a[i].v,&a[i].b); if(a[i].v>=c) ans+=a[i].b,a[i].b=0; } sort(a+1,a+n+1); while(1) { int now=0; for(int i=n;i;i--) while(a[i].v+now<c&&a[i].b) now+=a[i].v,a[i].b--; for(int i=1;i<=n;i++) if(a[i].b) { now+=a[i].v,a[i].b--; break; } if(now>=c)ans++; else break; } printf("%d\n",ans); return 0; } |
「JoyOI1033」悠闲的漫步
给出一棵树，求出1号点出发的最远距离
搜索或者dp皆可
|
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 |
#include<cmath> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; int p; int f[1005],c[1005],d1[1005],d2[1005]; int dfs(int x) { if(f[x]!=-1)return f[x]; f[x]=1; if(d1[x])f[x]=max(dfs(d1[x])+1,f[x]); if(d2[x])f[x]=max(dfs(d2[x])+1,f[x]); return f[x]; } int main() { memset(f,-1,sizeof(f)); scanf("%d",&p); for(int i=2;i<=p;i++) { int x; scanf("%d",&x); scanf("%d%d",&d1[x],&d2[x]); } printf("%d\n",dfs(1)); return 0; } |
「JoyOI1034」尼克的任务
用f(i)表示到第i分钟，最大的休息时间
若i分钟没有工作开始，则更新f(i+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 |
#include<cmath> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; int n,K; int p[10005],t[10005],f[10005]; int main() { scanf("%d%d",&n,&K); for(int i=1;i<=K;i++) scanf("%d%d",&p[i],&t[i]); for(int i=2;i<=n;i++)f[i]=-inf; for(int i=1;i<=n;i++) { bool flag=0; for(int j=1;j<=K;j++) if(p[j]==i) { f[i+t[j]]=max(f[i+t[j]],f[i]); flag=1; } if(!flag)f[i+1]=max(f[i+1],f[i]+1); } printf("%d\n",f[n+1]); return 0; } |
「JoyOI1035」棋盘覆盖
二分图匹配经典问题，先把棋盘黑白染色
一色分为X部，另一色分为Y部，每个黑色点向周围连边，匈牙利算法求最大匹配数量
当然网络流也可以
|
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 |
#include<cmath> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long #define p(x,y) (x-1)*n+y using namespace std; int n,m,ans; int del[10005]; int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0}; int lk[10005]; bool vis[10005]; vector<int>e[10005]; bool find(int x) { for(int i=0;i<e[x].size();i++) if(!vis[e[x][i]]) { vis[e[x][i]]=1; if(!lk[e[x][i]]||find(lk[e[x][i]])) { lk[e[x][i]]=x; return 1; } } return 0; } void build(int x,int y) { for(int d=0;d<4;d++) { int dx=x+xx[d],dy=y+yy[d]; if(dx<1||dy<1||dx>n||dy>n)continue; if(!del[p(dx,dy)]) e[p(x,y)].push_back(p(dx,dy)); } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); del[p(x,y)]=1; } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(!del[p(i,j)]&&((i+j)&1))build(i,j); for(int i=1;i<=n*n;i++) if(!del[i]) { memset(vis,0,sizeof(vis)); if(find(i))ans++; } printf("%d\n",ans); return 0; } |
「JoyOI1036」统计数字
把所有数字排序，就能很方便地得出每个数字出现次数了
|
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 |
#include<cmath> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; int n,a[200005]; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+n+1); int cnt=0; for(int i=1;i<=n;i++) { cnt++; if(a[i]!=a[i+1]) { printf("%d %d\n",a[i],cnt); cnt=0; } } return 0; } |
「JoyOI1037」阶乘统计2
高精度乘法，维护非0的最后20位
|
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 |
#include<cmath> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; int n,k; struct data{ int begin,l,v[500005]; data(){ v[1]=1; l=begin=1; } friend void operator*(data &a,int b){ for(int i=a.begin;i<=a.begin+20&&i<=a.l;i++) a.v[i]*=b; for(int i=a.begin;i<=a.begin+20&&i<=a.l;i++) { a.v[i+1]+=a.v[i]/10; a.v[i]%=10; if(a.v[a.l+1])a.l++; while(!a.v[a.begin])a.begin++; } } }ans; int main() { scanf("%d%d",&n,&k); for(int i=1;i<=n;i++)ans*i; for(int i=ans.begin+k-1;i>=ans.begin;i--) printf("%d",ans.v[i]); return 0; } |
「JoyOI1038」忠诚
线段树入门题，线段树的学习材料应该比较多，这里提供一个模板供参考
|
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 |
#include<cmath> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; int m,n; int val[400005],ls[400005],rs[400005]; void build(int k,int l,int r) { ls[k]=l;rs[k]=r; int mid=(l+r)>>1; if(l==r) { scanf("%d",&val[k]); return; } build(k<<1,l,mid);build(k<<1|1,mid+1,r); val[k]=min(val[k<<1],val[k<<1|1]); } int query(int k,int x,int y) { int l=ls[k],r=rs[k],mid=(l+r)>>1; if(l==x&&y==r)return val[k]; int ans=inf; if(x<=mid) ans=min(ans,query(k<<1,x,min(mid,y))); if(y>mid) ans=min(ans,query(k<<1|1,max(mid+1,x),y)); return ans; } int main() { scanf("%d%d",&m,&n); build(1,1,m); for(int i=1;i<=n;i++) { int a,b; scanf("%d%d",&a,&b); printf("%d ",query(1,a,b)); } return 0; } |
「JoyOI1039」忠诚2
又一道线段树入门题
|
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 |
#include<cmath> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; int m,n; int val[400005],ls[400005],rs[400005]; void build(int k,int l,int r) { ls[k]=l;rs[k]=r; int mid=(l+r)>>1; if(l==r) { scanf("%d",&val[k]); return; } build(k<<1,l,mid);build(k<<1|1,mid+1,r); val[k]=min(val[k<<1],val[k<<1|1]); } int query(int k,int x,int y) { int l=ls[k],r=rs[k],mid=(l+r)>>1; if(l==x&&y==r)return val[k]; int ans=inf; if(x<=mid) ans=min(ans,query(k<<1,x,min(mid,y))); if(y>mid) ans=min(ans,query(k<<1|1,max(mid+1,x),y)); return ans; } void modify(int k,int x,int y) { int l=ls[k],r=rs[k],mid=(l+r)>>1; if(l==r) { val[k]=y;return; } if(x<=mid)modify(k<<1,x,y); else modify(k<<1|1,x,y); val[k]=min(val[k<<1],val[k<<1|1]); } int main() { scanf("%d%d",&m,&n); build(1,1,m); for(int i=1;i<=n;i++) { int p,a,b; scanf("%d%d%d",&p,&a,&b); if(p==1)printf("%d ",query(1,a,b)); else modify(1,a,b); } return 0; } |
「JoyOI1040」表达式计算
要求实现高精度加法的表达式计算
倒着扫一遍字符串，遇到数字就把它加到当前数字的最高位
遇到加号就把当前数字加入答案后清空
|
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 |
#include<cmath> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; int n; char ch[1505]; struct data{ int l,v[1505]; void clear(){ l=0; memset(v,0,sizeof(v)); } data friend operator+(data a,data b){ data c;c.clear(); c.l=max(a.l,b.l); for(int i=1;i<=c.l;i++) c.v[i]=a.v[i]+b.v[i]; for(int i=1;i<=c.l;i++) { c.v[i+1]+=c.v[i]/10; c.v[i]%=10; if(c.v[c.l+1])c.l++; } return c; } }ans,tmp; int main() { scanf("%s",ch+1); n=strlen(ch+1); for(int i=n;i;i--) if(ch[i]=='+') { ans=ans+tmp; tmp.clear(); } else tmp.v[++tmp.l]=ch[i]-'0'; ans=ans+tmp; for(int i=ans.l;i;i--) printf("%d",ans.v[i]); return 0; } |
「JoyOI1041」表达式计算2
要求从左往右计算才不会出现复数
用两个栈从右往左把操作和数字都记下来
然后倒过来高精度计算
|
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 |
#include<cmath> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; int n,top; char ch[305]; bool opt[305]; struct data{ int l,v[1505]; void clear(){ l=0; memset(v,0,sizeof(v)); } data friend operator+(data a,data b){ data c;c.clear(); c.l=max(a.l,b.l); for(int i=1;i<=c.l;i++) c.v[i]=a.v[i]+b.v[i]; for(int i=1;i<=c.l;i++) { c.v[i+1]+=c.v[i]/10; c.v[i]%=10; if(c.v[c.l+1])c.l++; } return c; } data friend operator-(data a,data b){ data c;c.clear(); c.l=a.l; for(int i=1;i<=c.l;i++) if(a.v[i]>=b.v[i]) c.v[i]=a.v[i]-b.v[i]; else c.v[i]=a.v[i]+10-b.v[i],a.v[i+1]--; while(c.l&&!c.v[c.l])c.l--; return c; } }ans,tmp[305]; int main() { scanf("%s",ch+1); n=strlen(ch+1); top=1; for(int i=n;i;i--) if(ch[i]=='+')opt[top]=0,top++; else if(ch[i]=='-')opt[top]=1,top++; else tmp[top].v[++tmp[top].l]=ch[i]-'0'; ans=tmp[top]; for(int i=top-1;i;i--) if(opt[i])ans=ans-tmp[i]; else ans=ans+tmp[i]; for(int i=ans.l;i;i--) printf("%d",ans.v[i]); return 0; } |
「JoyOI1042」表达式计算3
先预处理把乘方变成乘法，然后从左到右计算
用一个临时的变量tmp来处理运算的优先级，即把一连串的乘除一起算完，再考虑加入答案
遇到一个加减符号就把tmp记入答案，tmp重新赋值
否则用tmp进行运算
|
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 |
#include<cmath> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; int n,top=1,top2=1; char ch[105]; int opt[105],num[105]; int opt2[105],num2[105]; int main() { scanf("%s",ch+1); n=strlen(ch+1); for(int i=1;i<=n;i++) if(ch[i]>='0'&&ch[i]<='9')num[top]=num[top]*10+ch[i]-'0'; else { top++; if(ch[i]=='+')opt[top]=1; if(ch[i]=='-')opt[top]=2; if(ch[i]=='*')opt[top]=3; if(ch[i]=='/')opt[top]=4; if(ch[i]=='^')opt[top]=5; } for(int i=2;i<=top;i++) if(opt[i]==5) for(int j=1;j<num[i];j++) { opt2[++top2]=3; num2[top2]=num[i-1]; } else opt2[++top2]=opt[i],num2[top2]=num[i]; int tmp=num[1],ans=0; for(int i=2;i<=top2;i++) { if(opt2[i]==1)ans+=tmp,tmp=num2[i]; if(opt2[i]==2)ans+=tmp,tmp=-num2[i]; if(opt2[i]==3)tmp*=num2[i]; if(opt2[i]==4)tmp/=num2[i]; } printf("%d\n",ans+tmp); return 0; } |
「JoyOI1043」表达式计算4
正经的表达式计算
用一个数字栈+操作栈来实现
从左往右，将扫到的数字入数字栈，将扫到的操作与操作栈的栈顶对比优先级
如果当前操作优先级高，将其入栈
否则从数字栈中取出两个数字，用栈顶的操作进行运算
优先级次序是右括号和栈内左括号，加减，乘除，乘方，未入栈的左括号
|
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 |
#include<cmath> #include<queue> #include<stack> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; stack<ll> num; stack<char> opt; int n,brack; string str; int pri(char opt) { if(opt=='+'||opt=='-')return 1; if(opt=='*'||opt=='/')return 2; if(opt=='^')return 3; if(opt=='(')return 100; if(opt=='#')return -inf; return -100; } ll cal() { char tmp=opt.top();opt.pop(); ll b=num.top();num.pop(); ll a=num.top();num.pop(); if(tmp=='+')return a+b; if(tmp=='-')return a-b; if(tmp=='*')return a*b; if(tmp=='/')return a/b; ll ans=1; for(int i=1;i<=b;i++) ans*=a; return ans; } int main() { cin>>str;n=str.length(); for(int i=0;i<n;i++) if(str[i]=='(')brack++; else if(str[i]==')')brack--; while(brack>0) brack--,str+=")"; while(brack<0) brack++,str="("+str; str=str+'#';opt.push('#'); num.push(0); int i=0; while(str[i]!='#'||opt.top()!='#') { if(str[i]>='0'&&str[i]<='9') { ll tmp=0; while(str[i]>='0'&&str[i]<='9') tmp=tmp*10+str[i]-'0',i++; num.push(tmp); } else { if(pri(str[i])>pri(opt.top())) { if(str[i]=='(')str[i]='['; opt.push(str[i]),i++; } else { if(opt.top()=='[') opt.pop(),i++; else num.push(cal()); } } } cout<<num.top()<<endl; return 0; } |
「JoyOI1044」数字三角形
ans(i,j)表示走到(i,j)的最大路径和，从上往下一层一层递推
|
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 |
#include<cmath> #include<queue> #include<stack> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; int n; int a[1005][1005],ans[1005][1005]; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) { scanf("%d",&a[i][j]); ans[i][j]=-inf; } ans[1][1]=a[1][1]; for(int i=1;i<n;i++) for(int j=1;j<=i;j++) { ans[i+1][j]=max(ans[i+1][j],ans[i][j]+a[i+1][j]); ans[i+1][j+1]=max(ans[i+1][j+1],ans[i][j]+a[i+1][j+1]); } int mx=-inf; for(int i=1;i<=n;i++) mx=max(mx,ans[n][i]); printf("%d\n",mx); return 0; } |
计数器 9850648
OI 课件=>
OI 课件=>
黄学长为什么在做TYVJ傻逼题啊
黄学长恐怕是要带新人了，从此化身黄老师
Orz黄老师
Tyvj似乎挂了
现在可以了