總目錄詳見https://blog.csdn.net/mrcrack/article/details/84471041
做題原則，找不到測評位址的題不做。2018-11-28
重走長征路---OI每周刷題記錄---9月29日 2013
本周共計20題
測評位址：
bfs
1.細胞問題 //線上測評位址https://www.luogu.org/problemnew/show/P1451
2.Knight Moves //線上測評位址https://vjudge.net/problem/POJ-1915
dfs
3.特殊的質數肋骨 //線上測評位址https://www.luogu.org/problemnew/show/P1218
高精度
階乘統計
4.階乘統計 //線上測評位址http://codevs.cn/problem/2156/
5.階乘末尾的零 //線上測評位址http://codevs.cn/problem/2860/
6.階乘問題 //線上測評位址https://www.luogu.org/problemnew/show/P1134
7.計算n！的值 //線上測評位址https://www.luogu.org/problemnew/show/P1009
貪心
8.裝箱問題 //線上測評位址https://www.luogu.org/problemnew/show/P1049
dp
數字三角形2-4
9.數字三角形2 //線上測評位址http://codevs.cn/problem/2189/
10.數字三角形3 //線上測評位址http://codevs.cn/problem/2193/
11.數字三角形4 //線上測評位址http://codevs.cn/problem/2198/
12.最長不下降子序列 //線上測評位址http://codevs.cn/problem/1576/
13.最小中間和 //線上測評網站http://codevs.cn/problem/1382/
14.飛彈問題 //線上測評位址https://www.luogu.org/problemnew/show/P1020
15.均分紙牌 //線上測評位址https://www.luogu.org/problemnew/show/P1031
16.機器工廠 //線上測評位址https://www.luogu.org/problemnew/show/P1376
17.機器配置設定 //線上測評位址https://www.luogu.org/problemnew/show/P2066
dfs
18.素數環 //線上測評位址https://vjudge.net/problem/HDU-1016
模拟
19.黑色星期五 //線上測評位址https://www.luogu.org/problemnew/show/P1202
20.單數？雙數？ //線上測評位址http://codevs.cn/problem/2163/
題解：
bfs
1.細胞問題
//P1451 求細胞數量
//線上測評位址https://www.luogu.org/problemnew/show/P1451
//每bfs一次，算一個細胞，同時把遇到的非0值置0
//算法的時間複雜度，若測試資料整個為1個細胞，100*100*(100)=10^6
//若測試資料整個為0個細胞，100*100=10^4
//樣例通過，送出AC。2018-12-10
#include <stdio.h>
#include <string.h>
char s[110][110];
int next[][2]={{-1,0},{1,0},{0,-1},{0,1}};//上下左右
int vis[110][110],m,n;//突然想到vis[][]還可以有二維形式，開竅了。
struct Point{
int x,y;
}q[12000],p;
void bfs(int x,int y){
int h,t,nx,ny,i;
h=t=1;
q[t].x=x,q[t].y=y,vis[x][y]=1,s[x][y]='0',t++;
while(h<t){
p=q[h];
for(i=0;i<4;i++){
nx=p.x+next[i][0];
ny=p.y+next[i][1];
if(0<=nx&&nx<m&&0<=ny&&ny<n&&vis[nx][ny]==0&&s[nx][ny]!='0'){
s[nx][ny]='0',vis[nx][ny]=1;
q[t].x=nx,q[t].y=ny,t++;
}
}
h++;
}
}
int main(){
int i,j,cnt=0;
memset(vis,0,sizeof(vis));
scanf("%d%d",&m,&n);
for(i=0;i<m;i++)
scanf("%s",s[i]);
for(i=0;i<m;i++)//此處寫成 for(i=0;i<n;i++) 昏招
for(j=0;j<n;j++)//此處寫成 for(j=0;j<m;j++) 昏招
if(s[i][j]!='0'){
cnt++;
bfs(i,j);
}
printf("%d\n",cnt);
return 0;
}
2.Knight Moves
//Knight Moves POJ - 1915
//線上測評位址https://vjudge.net/problem/POJ-1915
//借助 題圖，樣例，還是弄懂了該題。一個單詞都沒查
//寫代碼的過程有些失誤，但還是通過靜态檢查找到了問題。
//q[t].s=s+1,t++;//此處寫成 t++,q[t].s=s+1;
//樣例通過，送出Runtime Error。
//仔細看了看，大意了， q[100000];//此處寫成 q[10000]
//修改，送出AC。2018-12-10 20:23
#include <stdio.h>
#include <string.h>
int next[][2]={{-1,-2},{-2,-1},{-2,1},{-1,2},{1,-2},{2,-1},{2,1},{1,2}};
int vis[310][310],n;
struct Point{
int r,c,s;
}q[100000];//此處寫成 q[10000]
void bfs(int sr,int sc,int er,int ec){
int h,t,r,c,s,i,nr,nc;
h=t=1;
q[t].r=sr,q[t].c=sc,q[t].s=0,t++,vis[sr][sc]=1;
while(h<t){
r=q[h].r,c=q[h].c,s=q[h].s;
if(r==er&&c==ec){
printf("%d\n",s);
return;
}
for(i=0;i<8;i++){
nr=r+next[i][0],nc=c+next[i][1];
if(0<=nr&&nr<n&&0<=nc&&nc<n&&vis[nr][nc]==0){
vis[nr][nc]=1,q[t].r=nr,q[t].c=nc,q[t].s=s+1,t++;//此處寫成 t++,q[t].s=s+1;
}
}
h++;
}
}
int main(){
int t,sr,sc,er,ec;
scanf("%d",&t);
while(t--){
memset(vis,0,sizeof(vis));
scanf("%d",&n);
scanf("%d%d%d%d",&sr,&sc,&er,&ec);
bfs(sr,sc,er,ec);
}
return 0;
}
dfs
3.特殊的質數肋骨
//P1218 [USACO1.5]特殊的質數肋骨 Superprime Rib
//線上測評位址https://www.luogu.org/problemnew/show/P1218
//一開始想用質數篩，但一看99999999，即10^9，O(n)明顯逾時
//還是用深搜。
//原以為會挺慢，測試下來，速度驚人。樣例通過，送出AC。2018-12-12
//該題還有一個辦法，打表。
#include <stdio.h>
#include <string.h>
int n,a[15];
int isPrime(int x){//質數 傳回1，非質數傳回 0
int i;
if(x==1)return 0;
if(x==2)return 1;
for(i=2;i*i<=x;i++)
if(x%i==0)return 0;
return 1;
}
void dfs(int step){
int i,k,ans;
if(step==n+1){
ans=0;
for(k=1;k<=n;k++)//此處寫成 for(k=1;k<=n;i++) 真是昏到家了。
ans*=10,ans+=a[k];
if(isPrime(ans))printf("%d\n",ans);
return ;
}
for(i=1;i<=9;i++){
ans=0,a[step]=i;//此處寫成a[k]=i//漏了此句a[k]=i
for(k=1;k<=step;k++)
ans*=10,ans+=a[k];
if(isPrime(ans))
dfs(step+1);
}
}
int main(){
scanf("%d",&n);
dfs(1);
return 0;
}
高精度
階乘統計
4.階乘統計
//2156 階乘統計
//線上測評位址http://codevs.cn/problem/2156/
//long long 2^63=9223372036854775808
// 20!=2432902008176640000
//故，該題long long不會溢出
//對long long與int混搭，心存疑慮，立馬測試，之後解惑。
//樣例通過，送出AC。2018-12-10
#include <stdio.h>
#define LL long long
int out[20];//輸出的數
int main(){
LL ans=1,b;
int n,k,i,len;
scanf("%d%d",&n,&k);
for(i=1;i<=n;i++)
ans*=i;
while(ans%10==0)ans/=10;//去尾部的0
len=0,b=ans;
while(b){
out[len++]=b%10;
b/=10;
}
if(k>=len)printf("%lld",ans);
else
for(i=k-1;i>=0;i--)
printf("%d",out[i]);
return 0;
}
5.階乘末尾的零
//2860 階乘末尾的零
//線上測評位址http://codevs.cn/problem/2860/
//思路，統計每個數的因數10,5,2的個數
//每一對2,5對應一個結果0，每一個10對應一個結果0
//注意:1000!有249個零。
//考慮統計用long long
//擔心10^8會逾時，測試了一下，估計能險過
//送出AC.2018-12-10
#include <stdio.h>
#include <string.h>
#define LL long long
int min(LL a,LL b){
return a<b?a:b;
}
int main(){
LL cnt_2=0,cnt_5=0,cnt_10=0;
int i,n,m;
scanf("%d",&n);
for(i=1;i<=n;i++){
m=i;
while(m%10==0)m/=10,cnt_10++;
while(m%5==0)m/=5,cnt_5++;
while(m%2==0)m/=2,cnt_2++;
}
printf("%lld\n",cnt_10+min(cnt_2,cnt_5));
return 0;
}
6.階乘問題
//P1134 階乘問題
//線上測評位址https://www.luogu.org/problemnew/show/P1134
//思路，統計每個數的因數5,2的個數
//每一個10對應一個結果0若該數是10的整數倍，可直接跳過，不影響結果
//每一對2,5對應一個結果0，
//注意:注意:10,000,000!有2499999個零。
//考慮統計用long long
//擔心5*10^7會逾時，測試了一下，估計能險過
//送出AC.2018-12-10 對此次算法表示滿意，全是自己編的。
#include <stdio.h>
#define LL long long
int main(){
LL cnt_2=0,cnt_5=0,i;
int n,m,ans=1;
scanf("%d",&n);
for(i=1;i<=n;i++){
m=i;
if(m%10==0)m/=10;
while(m%5==0)m/=5,cnt_5++;
while(m%2==0)m/=2,cnt_2++;
ans=(ans*m)%10;
}
if(cnt_2>cnt_5)
for(i=1;i<=cnt_2-cnt_5;i++)
ans=(ans*2)%10;
else if(cnt_2<cnt_5)
for(i=1;i<=cnt_5-cnt_2;i++)
ans=(ans*5)%10;
printf("%d\n",ans);
return 0;
}
7.計算n！的值
//P1009 階乘之和
//線上測評位址https://www.luogu.org/problemnew/show/P1009
//看完題目，就知道該用，高精度加法+高精度乘法
//用高精度，總感覺挺糟糕的，代碼量不小啊
//該開多大的數組呢，先開大的吧，開到int z[2000]
//之後，測試n=50,再将上述數組 縮小範圍。
//循環次數，外層循環(1+50)*50/2=1275，内部循環，大約沒算一次大約1000，大緻感覺不會逾時
//先編一個主體程式，再編高精度乘，隻有才是高精度加
//編的過程中，記得及時測試，否則，怎麼錯都不知道。
//該題的優點是，高精度乘 發生在 數字*整數數組，編起來，相對簡單些
//為了盡可能的避免，運算過程中int的溢出，準備對f[]采用long long
//突然想到n!=(n-1)!*n應該能省不少時間
//z[i]+=y[i]+x[i];//此處寫成z[i]=y[i]+x[i];查了好久 花了30分鐘。
//測試了50的答案為31035053229546199656252032972759319953190362094566672920420940313
//maxn 開到 100即可
//測了一下，n=500反應也很快。決定将maxn開到1000
//樣例通過，送出AC。2019-1-15 21:13
//翻看了之前，編寫的代碼，在伯仲之間，各有優缺點。
//詳見https://blog.csdn.net/mrcrack/article/details/78473644
//1173 階乘和
#include <stdio.h>
#include <string.h>
#define maxn 1000
#define LL long long
LL f[maxn],ans[maxn],g[maxn];
void mul(int a,LL *f){
int i;
for(i=1;i<=f[0];i++)f[i]*=a;
for(i=1;i<=f[0];i++){//進位處理
f[i+1]+=f[i]/10;
f[i]%=10;
}
if(0<f[i]&&f[i]<10)f[0]=i;
else if(f[i]>=10){
while(f[i]>=10){
f[i+1]+=f[i]/10;
f[i]%=10;
i++;
}
f[0]=i;
}
}
void add(LL *x,LL *y,LL *z){
int i;
z[0]=y[0]>x[0]?y[0]:x[0];
for(i=1;i<=z[0];i++){
z[i]+=y[i]+x[i];//此處寫成z[i]=y[i]+x[i];查了好久
z[i+1]+=z[i]/10;
z[i]%=10;
}
if(z[i])z[0]=i;
}
int main(){
int n,i;
memset(ans,0,sizeof(0));
scanf("%d",&n);
memset(f,0,sizeof(f));
f[0]=1,f[1]=1;
for(i=1;i<=n;i++){
mul(i,f);
memset(g,0,sizeof(g));//漏了此句
add(f,ans,g);
memcpy(ans,g,sizeof(g));
}
for(i=ans[0];i>=1;i--)printf("%lld",ans[i]);
return 0;
}
貪心
8.裝箱問題
//P1049 裝箱問題
//NOIP 2001 普及組
//線上測評位址https://www.luogu.org/problemnew/show/P1049
//01背包問題，将物品的體積看成體積、價值即可。
//樣例通過，送出AC。2018-12-9 15:31
#include <stdio.h>
#include <string.h>
int v[35],f[35][20100];
int max(int a,int b){
return a>b?a:b;
}
int main(){
int m,n,i,j;
memset(f,0,sizeof(f));
scanf("%d%d",&m,&n);
for(i=1;i<=n;i++)
scanf("%d",&v[i]);
for(i=1;i<=n;i++)
for(j=0;j<=m;j++)
if(j<v[i])
f[i][j]=f[i-1][j];
else
f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+v[i]);
printf("%d\n",m-f[n][m]);
return 0;
}
dp
數字三角形2-4
9.數字三角形2
//2189 數字三角形W
//線上測評位址http://codevs.cn/problem/2189/
//沒什麼好辦法，深搜dfs
//擔心的是，逾時，試試看吧，沒有辦法的辦法
//該題，節點上最大值未告知，不過還是能應付的，a[i][j]%=100;//防止資料計算int溢出 100*25=2500
//樣例通過，送出，測試點1,2WA。2019-1-14 20:24
//發現問題，dfs(a[1][1],1,1,1);//此處寫成 dfs(0,1,1,1);
//修改，送出AC。2019-1-14 20:35
#include <stdio.h>
#include <string.h>
int n,a[30][30],b,c,sum,ans=0;
int max(int a,int b){
return a>b?a:b;
}
void dfs(int sum,int step,int r,int c){//r行 c列
int i,j;
if(step==n){
ans=max(ans,sum%100);
return ;
}
for(j=0;j<2;j++)
dfs(sum+a[r+1][c+j],step+1,r+1,c+j);
}
int main(){
int i,j;
memset(a,0,sizeof(a));
scanf("%d",&n);
for(i=1;i<=n;i++)
for(j=1;j<=i;j++){
scanf("%d",&a[i][j]);
a[i][j]%=100;//防止資料計算int溢出 100*25=2500
}
dfs(a[1][1],1,1,1);//此處寫成 dfs(0,1,1,1);
printf("%d\n",ans);
}
10.數字三角形3
//2193 數字三角形WW
//線上測評位址http://codevs.cn/problem/2193/
//一度想放棄，想看懂 數字三角形2 遞推的解答，
//試圖用在 該題上，無奈，一時難以看懂，隻好回到深搜dfs的老路上。
//在想，在亂搜中，如何過指定的點，遇到非指定點就跳過去，
//一個想法突然冒出來，這不就是剪枝嗎，太高興了，算法有了。2019-1-15 06:08
//該題有個缺點，沒說節點的最大值，在考慮int是否溢出
//樣例通過，送出AC。2019-1-15 剪枝有些感覺了
#include <stdio.h>
#include <string.h>
#define maxn 30
int n,a[maxn][maxn],ans=-999999999;
int max(int a,int b){
return a>b?a:b;
}
void dfs(int step,int sum,int r,int c){
int j;
if(r==n/2&&c!=n/2)//剪枝
return;
if(step==n){
ans=max(ans,sum);
return ;
}
for(j=0;j<2;j++)
dfs(step+1,sum+a[r+1][c+j],r+1,c+j);
}
int main(){
int i,j;
scanf("%d",&n);
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
scanf("%d",&a[i][j]);//此處寫成scanf("%d",&a[i]);，昏招
dfs(1,a[1][1],1,1);
printf("%d\n",ans);
return 0;
}
11.數字三角形4
//2198 數字三角形WWW
//線上測評位址http://codevs.cn/problem/2198/
//有了 剪枝 這個 技能，該題也就有信心了。
//該題的問題是，節點的最大值是多少，沒說，存在int可能溢出的情況。
//樣例通過，送出AC。2019-1-15 08:39
#include <stdio.h>
#include <string.h>
#define maxn 30
int n,a[maxn][maxn],x,y,ans=-999999999;
int max(int a,int b){
return a>b?a:b;
}
void dfs(int sum,int step,int r,int c){
int j;
if(r==x&&c!=y)return;//剪枝
if(step==n){
ans=max(ans,sum);
return ;
}
for(j=0;j<2;j++)
dfs(sum+a[r+1][c+j],step+1,r+1,c+j);
}
int main(){
int i,j;
memset(a,0,sizeof(a));
scanf("%d",&n);
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
scanf("%d",&a[i][j]);
scanf("%d%d",&x,&y);
dfs(a[1][1],1,1,1);
printf("%d\n",ans);
return 0;
}
12.最長不下降子序列
//最長不下降子序列 此題不好找，無奈找下題替換
//1576 最長嚴格上升子序列
//線上測評位址http://codevs.cn/problem/1576/
//樣例通過，送出AC。2018-12-19
#include <stdio.h>
#define maxn 5100
int a[maxn],d[maxn];
int max(int a,int b){
return a>b?a:b;
}
int main(){
int n,i,j,len=-1;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
for(i=1;i<=n;i++){
d[i]=1;
for(j=1;j<i;j++)
if(a[j]<a[i]&&d[j]+1>d[i])
d[i]=d[j]+1,len=max(len,d[i]);
}
printf("%d\n",len);
return 0;
}
13.最小中間和
//最小中間和 找不到 線上測評，隻好找 基本類似 來替換
//1382 沙子合并
//線上測評網站http://codevs.cn/problem/1382/
//f[i][j] i->j之間的 最小和
//開一個字首和b[i] 1->i的和
//f[i][i]=0;//此處真是，神來之筆
//最小的中間和的動歸，完全是獨立想出，高興。
//樣例通過，送出AC。2018-12-21
#include <stdio.h>
#include <string.h>
#define maxn 310
int a[maxn],f[maxn][maxn],b[maxn];
int min(int a,int b){
return a<b?a:b;
}
int main(){
int i,j,n,k;
scanf("%d",&n);
memset(f,127,sizeof(f)),b[0]=0;
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
f[i][i]=0;//此處真是，神來之筆
b[i]+=b[i-1]+a[i];
}
if(n==1){//特判，省得添堵
printf("%d\n",a[n]);
return 0;
}
for(k=1;k<=n-1;k++)
for(i=1;i<=n;i++)
if(i+k<=n)
for(j=i;j<=i+k;j++)
f[i][i+k]=min(f[i][i+k],f[i][j]+f[j+1][i+k]+b[i+k]-b[i-1]);
printf("%d\n",f[1][n]);
return 0;
}
14.飛彈問題
//P1020 飛彈攔截
//NOIP 普及組 1999
//線上測評位址https://www.luogu.org/problemnew/show/P1020
//開數組d[]存儲遞減序列
//二分法，找目前資料放置d[]數組中位置。
//樣例通過，送出AC。2018-12-14 22:07
//算法時間複雜度，O(nlogn).
#include <stdio.h>
int a[100100],d[100100];
int main(){
int i,k=1,ans1=0,left,right,mid,ans2=0;
while(scanf("%d",&a[k])!=EOF)k++;
d[0]=60000;
for(i=1;i<k;i++)//遞減序列處理
if(d[ans1]>=a[i])
ans1++,d[ans1]=a[i];//d[]是遞減序列
else{
left=0,right=ans1;
while(left+1<right){
mid=(left+right)/2;
if(d[mid]>=a[i])left=mid;//此處寫成 if(d[ans1]>=a[i])left=mid;
else right=mid;
}
d[right]=a[i];//目标，讓該遞減序列，每個位置的值都盡可能大
}
printf("%d\n",ans1);
d[0]=-1;
for(i=1;i<k;i++)//嚴格遞增序列處理
if(d[ans2]<a[i])
ans2++,d[ans2]=a[i];
else{
left=0,right=ans2;
while(left+1<right){
mid=(left+right)/2;
if(d[mid]<a[i])left=mid;
else right=mid;
}
d[right]=a[i];//想清資料存儲格式，采用left還是right，自然明白
}
printf("%d\n",ans2);
return 0;
}
//P1020 飛彈攔截
//NOIP 普及組 1999
//線上測評位址https://www.luogu.org/problemnew/show/P1020
//最長不上升子序列 飛彈個數
//最長上升降子序列 攔截系統套數
//樣例通過，送出WA，隻通過了測試點1.
//修改if(a[j]<a[i]&&d[j]+1>d[i])//計算攔截系統，此處寫成 if(a[j]<=a[i]&&d[j]+1>d[i])。
//送出，測試點1-10 AC，O(n^2)通過。2018-12-12 17:30
#include <stdio.h>
#include <string.h>
int a[100100],d[100100];
int max(int a,int b){
return a>b?a:b;
}
int main(){
int k=0,i,j,ans1=-1,ans2=-1;
while(scanf("%d",&a[k])!=EOF)k++;
for(i=0;i<k;i++){
d[i]=1;
for(j=0;j<i;j++)
if(a[j]>=a[i]&&d[j]+1>d[i])
d[i]=d[j]+1,ans1=max(ans1,d[i]);
}
for(i=0;i<k;i++){
d[i]=1;
for(j=0;j<i;j++)
if(a[j]<a[i]&&d[j]+1>d[i])//計算攔截系統，此處寫成 if(a[j]<=a[i]&&d[j]+1>d[i])
d[i]=d[j]+1,ans2=max(ans2,d[i]);
}
printf("%d\n%d\n",ans1,ans2);
return 0;
}
15.均分紙牌
//P1031 均分紙牌
//NOIP 2002 提高組
//線上測評位址https://www.luogu.org/problemnew/show/P1031
//純模拟，由左往右開始填坑。
//很是高興，一次送出，就AC。沒有參考任何其它。2018-12-19
//樣例過程如下
9 8 17 6
10 7 17 6
10 10 14 6
10 10 10 10
#include <stdio.h>
#define maxn 110
int a[maxn];
int main(){
int n,i,avg=0,cnt=0;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]),avg+=a[i];
avg/=n;
for(i=1;i<n;i++)
if(a[i]!=avg)
a[i+1]+=a[i]-avg,cnt++;//a[i]多移走，少補進
printf("%d\n",cnt);
return 0;
}
16.機器工廠
//P1376 機器工廠
//線上測評位址https://www.luogu.org/problemnew/show/P1376
//吐糟該題，看了半天沒看懂，出題人的第一要務，要讓人看懂題
//若無能力表述清楚，至少，應将給出的樣例解釋清楚。
//對樣例進行解釋
4 5 共4周 每周每台保管費5
88 200 第1周 每台費用88 需200台
89 400 第2周 每台費用89 需400台
97 300 第3周 每台費用97 需300台
91 500 第3周 每台費用91 需500台
該樣例資料計算
第1周 每台費用 88 需200 花銷88*200
第2周 每台費用 93 89 需400 花銷89*400
第3周 每台費用 98 94 97 需300 花銷94*300
第4周 每台費用 103 99 102 91 需300 花銷91*300
總花銷126900
//有了基本算法，在一堆價格中，取最小值,進行計算
//采用O(n)的算法
//總花銷，最大值5000*10000=5*10^7 int不會溢出
//樣例通過，送出90分，測試點6 WA.
//翻看題解，表示，不服，怎麼會用到long long
//反複讀題，才發現，每周最多10000台，每台最多花費5000，最多10000周
//那麼最大值10000*5000*10000=5*10^11，現在同意用long long了
//long long cost=0;//之前寫成 int cost=0;交90分，測試點6 WA.
//修改，送出AC。2019-1-16
//大意失荊州，題目還是要多讀，最好還是要動紙筆。
#include <stdio.h>
#include <string.h>
#define maxn 10100
int n,s,a,b;//b該周的費用，a該周之前一周的費用
int min(int a,int b){
return a<b?a:b;
}
int main(){
int i,y;
long long cost=0;//之前寫成 int cost=0;交90分，測試點6 WA.
a=999999999;
scanf("%d%d",&n,&s);
for(i=1;i<=n;i++){
scanf("%d%d",&b,&y);
a=min(a+s,b);
cost+=a*y;
}
printf("%lld\n",cost);
return 0;
}
17.機器配置設定
//P2066 機器配置設定
//線上測評位址https://www.luogu.org/problemnew/show/P2066
//線上測評位址http://ybt.ssoier.cn:8088/problem_show.php?pid=1266
//在兩個線上測評網址之間切換，總算弄懂了題意。
//解釋樣例：
//公司1選3台 盈利50
//公司2選3台 盈利50
//公司3選3台 盈利30
//公司1選1台 盈利30 公司2選1台 盈利20 公司3選1台 盈利20 總共盈利 70
//f[i][j] i台機器 被 j個公司選 的最大盈利值
//列印 分公司編号和該分公司獲得裝置台數。沒什麼感覺
//那麼，将動歸的中間過程列印，找規律。
//發現
//f[1][1]=30,f[0][0]=0 i=1 j=1 k=1
//f[2][2]=50,f[1][1]=30 i=2 j=2 k=1
//f[3][3]=70,f[2][2]=50 i=3 j=3 k=1
//找到規律，以遞歸的方式列印結果。
//樣例通過，送出10分，測試點2-10WA。2019-1-15 17:07
//有多組解的情況處理，if(f[i][j]<=f[i-1][j-k]+a[i][k]){//此處寫成 if(f[i][j]<f[i-1][j-k]+a[i][k])
//送出20分，測試點3-10WA。2019-1-15 17:10
//翻看了之前的代碼https://blog.csdn.net/mrcrack/article/details/78440134
//發現for(k=0;k<=j;k++)//此處寫成for(k=1;k<=j;k++)
//就這一處差别，造成了 20分 與 100分 的差距。2019-1-15 17:16
//覺的又困惑，針對樣例，将for(k=0;k<=j;k++)的資料列印如下
f[1][1]=30 f[1][2]=40 f[1][3]=50
f[2][1]=30 f[2][2]=50 f[2][3]=60
f[3][1]=30 f[3][2]=50 f[3][3]=70
//将for(k=1;k<=j;k++)的資料列印如下
f[1][1]=30 f[1][2]=40 f[1][3]=50
f[2][1]=20 f[2][2]=50 f[2][3]=60
f[3][1]=20 f[3][2]=40 f[3][3]=70
//各位看到差别了嗎.2019-1-15 17:20
//該題編寫，還是比較滿意的，除了一處k=0還是k=1是翻看之前的編寫記錄，其它都是獨立編寫，且獨立改正的。2019-1-15 17:29
#include <stdio.h>
#include <string.h>
int a[15][20],f[15][20],g[15][20];
void print(int x,int y){//選擇了x個公司,選擇了y件機器
if(x==0)return;
print(x-1,y-g[x][y]);
printf("%d %d\n",x,g[x][y]);
}
int main(){
int n,m,i,j,k;
memset(f,0,sizeof(f));
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
scanf("%d",&a[i][j]);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
for(k=0;k<=j;k++)//此處寫成for(k=1;k<=j;k++)//這是最關鍵的一行代碼
if(f[i][j]<=f[i-1][j-k]+a[i][k]){//此處寫成 if(f[i][j]<f[i-1][j-k]+a[i][k])
f[i][j]=f[i-1][j-k]+a[i][k];
g[i][j]=k;//選擇了x個公司,選擇了y件機器 ,此次需加入的機器數量k
}
printf("%d\n",f[n][m]);
print(n,m);
return 0;
}
dfs
18.素數環
//Prime Ring Problem HDU - 1016
//線上測評位址https://vjudge.net/problem/HDU-1016
//回溯+深搜
//要點，頭尾兩數和為質數
//送出Wrong Answer，發現 k++,printf("\nCase %d:\n",k);//此處寫成 k++,printf("\nCase k:\n");
//送出Wrong Answer，估計 格式的 問題，繼續修改
//覺得格式修改無誤了，送出，竟然出現Presentation Error
//好歹知道現在出現的問題，就是格式問題。
//再讀題，發現這麼一句Print a blank line after each case.
//繼續修改，送出AC。2018-12-12 一度想要求助網絡，不過，還是忍住了，獨立AC。
//ACM的送出方式，對格式要求真高。
#include <stdio.h>
#include <string.h>
int vis[30],a[30],n,kase=0;
int isPrime(int x){//質數 傳回1 非質數 傳回0
int i;
if(x==1)return 0;
if(x==2)return 1;
for(i=2;i*i<=x;i++)
if(x%i==0)return 0;
return 1;
}
void dfs(int step){
int i,k;
if(step==n+1){
if(n>=2&&isPrime(a[1]+a[n])){//此處寫成 if(isPrime(a[1]+a[n])
printf("%d",a[1]);
for(k=2;k<=n;k++)
printf(" %d",a[k]);
printf("\n");
}
return;
}
for(i=1;i<=n;i++)
if(vis[i]==0&&isPrime(a[step-1]+i)){
vis[i]=1,a[step]=i;
dfs(step+1);
vis[i]=0;
}
}
int main(){
while(scanf("%d",&n)!=EOF){
memset(vis,0,sizeof(vis));
kase++;
printf("Case %d:\n",kase);//此處寫成 k++,printf("\nCase k:\n");
a[1]=1,vis[1]=1;
dfs(2);
printf("\n");//少了此句
}
return 0;
}
模拟
19.黑色星期五
//P1202 [USACO1.1]黑色星期五Friday the Thirteenth
//線上測評位址https://www.luogu.org/problemnew/show/P1202
//看了看該題，有點煩，編好該題，對日期的處理應是手到擒來。
//閏年判定函數，
//月天數數組。
//編完一個函數，或功能，測試是必需的。
//思路，算出每個月13号，從1900年開始的天數，再進行星期幾的計算。
//樣例通過，送出AC。2018-12-9 17:00
#include <stdio.h>
#include <string.h>
int month[]={0,31,28,31,30,31,30,31,31,30,31,30,31};//month[1]表示1月的天數
int week[10];
int run(int year){//閏年傳回1，平年傳回0
if(year%100==0)return year%400?0:1;//整百年
else return year%4?0:1;//非整百年
}
int main(){
int n,i,j,year,tot=0,day=0;//tot當年開始之前的總天數。 day=0當年開始的總天數
memset(week,0,sizeof(week));//week[1]周一，week[6]周六，week[0]周日
scanf("%d",&n);
for(i=0;i<n;i++){
year=1900+i;
month[2]=run(year)?29:28;
if(i>0)tot+=(365+run(year-1));
day=tot+13;
for(j=0;j<12;j++){
day+=month[j];
week[day%7]++;
}
}
printf("%d %d",week[6],week[0]);
for(i=1;i<=5;i++)
printf(" %d",week[i]);
return 0;
}
20.單數？雙數？
//2163 單數??雙數????
//線上測評位址http://codevs.cn/problem/2163/
//該題，資料(1 <= I <= 10^60)看起來挺吓人
//起始用字元串存儲，判斷最後一位是否奇偶即可
//樣例通過，送出AC。2018-12-9 21:18
#include <stdio.h>
#include <string.h>
char s[100];
int main(){
int t,len;
scanf("%d",&t);
while(t--){
scanf("%s",s);
len=strlen(s);
if((s[len-1]-'0')%2)printf("odd\n");
else printf("even\n");
}
return 0;
}
2019-1-16 AC 該周内容
![重走長征路---OI每周刷題記錄---11月4日 2013[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)