總目錄詳見https://blog.csdn.net/mrcrack/article/details/84471041
做題原則，找不到測評位址的題不做。2018-11-28
重走長征路---OI每周刷題記錄---11月4日 2013
本周共計22題
吐槽一下，該周不僅題目多，且不易。2019-1-29 07:55
測評位址：
dp
1.免費餡餅 //線上測評位址http://218.5.5.242:9018/JudgeOnline/problem.php?id=1142
2.石子合并 //線上測評位址https://www.luogu.org/problemnew/show/P1880
3.攔截飛彈 //線上測評位址http://218.5.5.242:9018/JudgeOnline/problem.php?id=1407
4.能量項鍊 //線上測評位址https://www.luogu.org/problemnew/show/P1063
5.找雷 //線上測評位址https://www.luogu.org/problemnew/show/P2196
并查集
6.親戚 //線上測評位址http://codevs.cn/problem/1073/
貪心
7.觀光公交
heap
8.合并果子 //線上測評位址https://www.luogu.org/problemnew/show/P1090
模拟
9.尋寶 //線上測評位址https://www.luogu.org/problemnew/show/P1076
hash
10.方程的解數 //線上測評位址http://codevs.cn/problem/1735/
數論
11.數列 //線上測評位址https://www.luogu.org/problemnew/show/P1062
12.同餘方程 //線上測評位址https://www.luogu.org/problemnew/show/P1082
13.多項式系數 //線上測評位址https://www.luogu.org/problemnew/show/P1313
dfs
14.選數 //線上測評位址https://www.luogu.org/problemnew/show/P1036
高精度
15.回文數 //線上測評位址https://www.luogu.org/problemnew/show/P1015
模拟
16.現在幾點鐘 //線上測評位址http://218.5.5.242:9018/JudgeOnline/problem.php?id=1063
17.選擇客棧 //線上測評位址https://www.luogu.org/problemnew/show/P1311
18.機器翻譯 //線上測評位址https://www.luogu.org/problemnew/show/P1540
19.電腦的改良 //線上測評位址https://www.luogu.org/problemnew/show/P1022
20.分數線劃定 //線上測評位址https://www.luogu.org/problemnew/show/P1068
進制
21.進制轉換 //線上測評位址https://www.luogu.org/problemnew/show/P1015
枚舉
22.一進制三次方程求解 //線上測評位址https://www.luogu.org/problemnew/show/P1024
題解：
dp
1.免費餡餅
//1142: 免費餡餅
//線上測評位址http://218.5.5.242:9018/JudgeOnline/problem.php?id=1142
//看題，沒什麼思路，查找網絡，此文https://blog.csdn.net/sbs2000/article/details/50670773給出思路
//由于餡餅下落的時間和速度都不同，人隻能向左右移動，餡餅隻能向下移動。人和餡餅都同時移動，思考起來比較複雜，是以我們需要轉變思路：
//算出每個時刻落到最底層的每個格子有多少分值的餡餅。
//如果将餡餅當成參照物，則餡餅向下落，可以看成餡餅不動，人往上走去摘取餡餅，這樣人每1時刻都可以走到上一行的5個格子，
//這道題是經典動規模型數塔的變形，将餡餅落下的位置看做數塔中的列數，将下落的時間看做數塔中的行數，問題轉化為求解從塔底到塔頂的最長路徑。
//以上為摘抄内容，開始獨立編寫。a[i][j]第i秒到達底部的j列的餡餅分數值
//該題考得比較全面，還需記錄路徑
//切記，編好一部分功能，須及時進行測試。
//分數值應該為非負，該題需進行說明。
//該題可能存在多解，不過題目未作說明，如何處理。
//編好，樣例無法通過，
//發現因需記錄路徑，無需再寫max函數了
//樣例通過，重新讀了代碼，發現有備援代碼，删改，
//送出，答案錯誤33%
//重讀題目，發現，時間最大值1000+100/1=1100,故[1100][110]需修改,
//仔細想了想，有一個開始位置，有一個結束位置，開始位置沒有考慮，可能不從0開始，開始誤以為從0開始
//修改，送出，答案錯誤50%。
//翻看http://hzwer.com/124.html代碼，才發現，有些餡餅竟然可以接不到,真是沒想到
//修改，送出，答案錯誤50%。2019-1-25 21:42
//發現數組a[][]未初始化，初始化後，送出，答案錯誤50%,2019-1-25 22:32
//突然間想到，既然有些餡餅接不到，那麼有些時間段，也可以沒有一塊餡餅
//故，代碼的最大值是沒有問題的，問題出在列印路徑上。
//列印路徑需判定，上一層若無，仔細想了想，這個想法不對
//反複讀代碼，讀題，發現，代碼寫得有問題，中間時間就算沒有餡餅了，人也可以做決策
//begin變量造成該題的問題，時間應該是從0開始的。而非從begin開始。
//修改，送出，答案錯誤33%。2019-1-25 22:52
//無奈，将http://hzwer.com/124.html代碼進行修改，不斷靠近自己代碼，每改動一點，送出AC，繼續改動
//終于發現自己代碼問題，b=0;擺錯位置，應該是在兩重循環之内，而非兩重循環之間
//修改，送出AC。2019-1-25 23:29 真不容易啊。
#include <stdio.h>
#include <string.h>
int a[1200][110],W,H,b,p[1200][110];//p[i][j]=k記錄路徑，a[i][j]來自 a[i+1][k]
int max(int a,int b){
return a>b?a:b;
}
int main(){
int i,j,start,h,d,v,pos,k,end=0;//pos起始位置
scanf("%d%d",&W,&H);
memset(a,0,sizeof(a));//漏了此句
while(scanf("%d%d%d%d",&start,&h,&d,&v)!=EOF){
if((H-1)%d==0){//漏了此舉判斷
end=max(end,start+(H-1)/d);
a[start+(H-1)/d][h]+=v;
}
}
for(i=end;i>=0;i--){//此處寫成for(i=end;i>=begin-1;i--)//此處寫成 for(i=t;i>=0;i--)
//b=0;放在此處查了好久，花了2小時
for(j=1;j<=W;j++){
b=0;//添加 ，花了2小時
if(j-2>=1&&b<a[i+1][j-2])b=a[i+1][j-2],k=j-2;
if(j-1>=1&&b<a[i+1][j-1])b=a[i+1][j-1],k=j-1;
if(b<a[i+1][j])b=a[i+1][j],k=j;
if(j+1<=W&&b<a[i+1][j+1])b=a[i+1][j+1],k=j+1;
if(j+2<=W&&b<a[i+1][j+2])b=a[i+1][j+2],k=j+2;
a[i][j]+=b,p[i][j]=k;
}
}
pos=(W+1)/2;
printf("%d\n",a[0][pos]);
for(i=0;i<end;i++){//此處寫成for(i=begin-1;i<end;i++)//此處寫成 for(i=0;i<t;i++)
printf("%d\n",p[i][pos]-pos);
pos=p[i][pos];
}
return 0;
}
2.石子合并
//P1880 [NOI1995]石子合并
//線上測評位址https://www.luogu.org/problemnew/show/P1880
//感覺要區分，順時針，逆時針，但動筆研究，發現不影響結果
//化圈為線，将N堆石子，變成N+N=2N堆石子即可，這樣就可以在數組中直接處理
//先寫最大得分。最小得分，照葫蘆畫瓢即可。
//單個石子的最大值，最小值，沒作說明，int是否溢出？
//編到後面，突然發現，弄明白樣例是關鍵
//該題缺一個樣例解釋啊，突然感覺，樣例沒弄明白
//4 5 9 4
// 9 9 4 9+
// 18 4 9+18
// 22 9+18+22=49
//
//4 5 9 4
// 9 13 9+13
// 22 9+13+22=44
//大緻弄明白了
//突然想到要用字首和，否則該題極難處理
//樣例通過，送出AC。2019-1-26 20:17
#include <stdio.h>
#include <string.h>
int n,a[210],dp1[210][210],dp2[210][210],sum[210];
int min(int a,int b){
return a<b?a:b;
}
int max(int a,int b){
return a>b?a:b;
}
int main(){
int i,j,k,p=999999999,q=-1;//p,q初始化，很重要。
memset(sum,0,sizeof(sum));
scanf("%d",&n);
memset(dp1,127,sizeof(dp1)),memset(dp2,0,sizeof(dp2));
for(i=1;i<=2*n;i++)dp1[i][i]=0;//此行很關鍵
for(i=1;i<=n;i++)scanf("%d",&a[i]),a[n+i]=a[i];
for(i=1;i<=2*n;i++)sum[i]+=sum[i-1]+a[i];
for(k=1;k<n;k++)
for(i=1;i<=2*n;i++)//此處寫成 for(i=1;i<=n;i++)
for(j=i;j<i+k;j++)//此處寫成 for(j=i;j<=i+k;j++)
if(i+k<=2*n){//補上此功能
dp1[i][i+k]=min(dp1[i][i+k],dp1[i][j]+dp1[j+1][i+k]+sum[i+k]-sum[i-1]);
dp2[i][i+k]=max(dp2[i][i+k],dp2[i][j]+dp2[j+1][i+k]+sum[i+k]-sum[i-1]);//此處寫成 dp[i][i+k]=max(dp[i][i+k],dp[i][j]+dp[i+j+1][i+k]);
}
for(i=1;i<=n;i++){
p=min(p,dp1[i][i+n-1]);
q=max(q,dp2[i][i+n-1]);
}
printf("%d\n%d\n",p,q);
return 0;
}
3.攔截飛彈
//1407: 攔截飛彈
//線上測評位址http://218.5.5.242:9018/JudgeOnline/problem.php?id=1407
//該題的難點在于，n<=100000，O(n^2)算法無法AC
//隻能采用O(nlogn)算法
//二分。
//樣例通過，送出83%，答案錯誤，翻看之前的編碼https://blog.csdn.net/mrcrack/article/details/84928209
//中的//P1020 飛彈攔截
//仔細想想，原來的寫法确實有問題，修改，送出AC。2019-1-17 21:02
//原來的寫法，極端情況，二分在f[1],f[2]結束
//現在的寫法，極端情況，在f[0],f[1]結束。
#include <stdio.h>
#define maxn 100100
int f[maxn],ans=0;//f[]是一個遞減序列
int main(){
int n,h,i,left,right,mid;
scanf("%d",&n);
f[0]=100100;//飛行高度不高于10^5
for(i=1;i<=n;i++){
scanf("%d",&h);
if(f[ans]>=h)ans++,f[ans]=h;//漏了此句 f[ans]=h
else{
left=0,right=ans;//此處寫成left=1//此處left指派很關鍵
while(left+1<right){
mid=(left+right)/2;
if(f[mid]<h)right=mid;
else left=mid;
}
f[right]=h;//此處寫成f[left]=h;
}
}
printf("%d\n",ans);
return 0;
}
4.能量項鍊
//P1063 能量項鍊
//NOIP 2006 提高組 第1題 共4題
//線上測評位址https://www.luogu.org/problemnew/show/P1063
//題目對樣例解釋得清清楚楚，出得好。
//化圈為線，由N個珠子變成2*N個珠子，處理起來就友善了
//題目連資料範圍都說得很清楚，真是出得好。
//并且說明了，順逆時針。試了下
//順時針
//1 2 3 4 (2,3)(3,5)(5,10)(10,2) 2*3*5+2*5*10+2*10*2=170
//2 3 4 1 (3,5)(5,10)(10,2)(2,3) 3*5*10+3*10*2+3*2*3=228
//3 4 1 2 (5,10)(10,2)(2,3)(3,5) 5*10*2+5*2*3+5*3*5=160
//4 1 2 3 (10,2)(2,3)(3,5)(5,10) 10*2*3+10*3*5+10*5*10=710
//逆時針
//1 4 3 2 (2,3)(10,2)(5,10)(3,5)頭尾接不上
//4 3 2 1
//3 2 1 4
//2 1 4 3
//顯然，逆時針不屬于該題，讨論的範圍。
//該題隻需考慮順時針的情況，松了口氣。
//樣例通過，送出10分，測試點1,3-10WA，不敢相信
//算法，沒問題，怎麼可能，重新讀題
//發現(4⊕1)=10×2×3=60，了解有誤，
//dp[i][i+k]=max(dp[i][i+k],dp[i][j]+dp[j+1][i+k]+a[i]*a[j+1]*a[i+k+1]);//此處寫成dp[i][i+k]=max(dp[i][i+k],dp[i][j]+dp[j+1][i+k]+a[i]*a[j+1]*a[i+k]);
//修改，送出0分，全WA，怎麼可能
//重讀代碼，發現，測試語句未删除
//删除測試語句，送出AC。2019-1-27 11:52
//真是一步錯，步步錯，焦頭爛額。
//讀好題目，了解好樣例是關鍵。
//突然有一個疑問，NOIP的複賽題，除了簡單輸入輸出資料外，還配了一個複雜的輸入輸出資料嗎？2019-1-27 11:57
#include <stdio.h>
#include <string.h>
int a[210],dp[210][210];
int max(int a,int b){
return a>b?a:b;
}
int main(){
int n,i,j,k,ans=-1;
memset(dp,0,sizeof(dp));
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&a[i]),a[n+i]=a[i];
for(k=1;k<n;k++)//此處寫成 for(k=2;k<n;k++),查了會
for(i=1;i<=2*n;i++)
for(j=i;j<i+k;j++)
if(i+k<2*n)//此處寫成 if(i+k<=2*n)
dp[i][i+k]=max(dp[i][i+k],dp[i][j]+dp[j+1][i+k]+a[i]*a[j+1]*a[i+k+1]);//此處寫成dp[i][i+k]=max(dp[i][i+k],dp[i][j]+dp[j+1][i+k]+a[i]*a[j+1]*a[i+k]);
for(i=1;i<=n;i++)ans=max(ans,dp[i][i+n-1]);
printf("%d\n",ans);
return 0;
}
5.找雷
//P2196 挖地雷
//NOIP 1996 提高組 第3題 共4題
//2019-1-28 20:30翻看了之前編寫的代碼https://blog.csdn.net/mrcrack/article/details/78440134
//2019-1-29 06:00發現就是最長上升子序列的變形
//感歎，當時能想出，現在怎麼沒想到呢。
//有進有退，進多退少，總體是進步的。2019-1-29 08:02
//開始編碼，有向圖，用來判定兩點是否聯通
//d[i]以i點為結尾的，挖的最多雷
//列印路徑過程，稍微有些小障礙，很快修改成功，
//樣例通過，送出AC。2019-1-29 08:17
#include <stdio.h>
#include <string.h>
int n,a[25],map[25][25],d[25],pre[25],last;//pre[i]=j i的上一個點來自j
void print_path(int k){
if(k==0)return;
print_path(pre[k]);
if(pre[k]==0)printf("%d",k);
else printf(" %d",k);
}
int main(){
int i,j,ans=0;
memset(map,0,sizeof(map)),memset(pre,0,sizeof(0));
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++)
scanf("%d",&map[i][j]);
for(i=1;i<=n;i++){
d[i]=a[i];
for(j=1;j<=n;j++)
if(map[j][i]&&d[j]+a[i]>d[i])
d[i]=d[j]+a[i],pre[i]=j;
}
for(i=1;i<=n;i++)
if(ans<d[i])
ans=d[i],last=i;
print_path(last);
printf("\n%d\n",ans);
return 0;
}
//P2196 挖地雷
//NOIP 1996 提高組 第3題 共4題
//線上測評位址https://www.luogu.org/problemnew/show/P2196
//N<=20，第1直覺，深搜dfs可行
//選擇一條路徑，又想到圖
//題目寫得很清楚，很好懂
//該題需列印路徑，需費些心
//看了樣例，發現是有向圖
//準備采用類Floyd算法，有些累了，先休息。2019-1-27 21:18
//考慮之後，決定用 深搜dfs試試，看看能不能解決路徑問題
//在列印路徑編寫過程中，發現，對遞歸了解更深刻了。
//出現最大值時，馬上存儲路徑，雖然之後的路徑會變。
//樣例通過，送出AC。深搜dfs水準确實高了許多。2019-1-28 13:55
#include <stdio.h>
#include <string.h>
int a[25],map[25][25],n,vis[25],ans=0,b[25],path[25];
void dfs(int step,int start,int sum){
int i,j;
if(ans<sum){
ans=sum;
path[0]=step;
for(j=1;j<=step;j++)path[j]=b[j];
}
for(i=1;i<=n;i++)
if(vis[i]==0&&map[start][i]==1){
vis[i]=1;
b[step+1]=i;
dfs(step+1,i,sum+a[i]);
vis[i]=0;
}
}
int main(){
int i,j;
memset(map,0,sizeof(map));
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++)
scanf("%d",&map[i][j]);
for(i=1;i<=n;i++){
memset(vis,0,sizeof(vis));
vis[i]=1;
b[1]=i;
dfs(1,i,a[i]);//此處寫成 dfs(1,i,0);
vis[i]=0;
}
printf("%d",path[1]);
for(i=2;i<=path[0];i++)printf(" %d",path[i]);
printf("\n%d\n",ans);
return 0;
}
并查集
6.親戚
//1073 家族
//線上測評位址http://codevs.cn/problem/1073/
//該題就是一個裸的并查集
//樣例很快通過，送出AC. 2019-1-18
#include <stdio.h>
#define maxn 5100
int n,m,p,f[maxn];
int getf(int u){
if(f[u]==u)return u;
return f[u]=getf(f[u]);
}
void merge(int u,int v){
int f1=getf(u),f2=getf(v);
if(f1!=f2)//左靠
f[f2]=f1;
}
int main(){
int i,x,y,f1,f2;
scanf("%d%d%d",&n,&m,&p);
for(i=1;i<=n;i++)f[i]=i;
while(m--){
scanf("%d%d",&x,&y);
merge(x,y);
}
while(p--){
scanf("%d%d",&x,&y);
f1=getf(x),f2=getf(y);
if(f1==f2)printf("Yes\n");
else printf("No\n");
}
return 0;
}
貪心
7.觀光公交
heap
8.合并果子
//P1090 合并果子
//NOIP 2004 提高組 第2題 共4題
//線上測評位址https://www.luogu.org/problemnew/show/P1090
//用該題演練STL中的堆函數
//樣例通過，送出AC。2019-1-28 20:42
//做個說明，彈出元素，從頂部,a[1]；加入元素，從尾部,a[n]
//預設是 大根堆。
//若要小根堆，需加cmp函數， a>b
//若加了cmp函數，則make,pop,push函數，均需加此cmp函數。否則，均無法實作功能。
//STL的堆函數處理堆問題，代碼量太小了。2019-1-28 20:45
#include <cstdio>
#include <algorithm>
using namespace std;
int n,h[10100];
int cmp(int a,int b){
return a>b;
}
int main(){
int i,ans=0,m,a,b;
scanf("%d",&n),m=n-1;
for(i=1;i<=n;i++)scanf("%d",&h[i]);
make_heap(h+1,h+1+n,cmp);
for(i=1;i<=m;i++){
a=h[1],pop_heap(h+1,h+1+n,cmp),n--;//此處寫成 pop_heap(h+1,h+1+n)
b=h[1],pop_heap(h+1,h+1+n,cmp);
ans+=a+b;
h[n]=a+b,push_heap(h+1,h+1+n,cmp);//此處寫成 push_heap(h+1,h+1+n)
}
printf("%d\n",ans);
return 0;
}
模拟
9.尋寶
//P1076 尋寶
//NOIP 2012 普及組 第2題 共4題
//線上測評位址https://www.luogu.org/problemnew/show/P1076
//題目很長，耐心多讀幾遍，很重要。
//弄懂題意最好的辦法，就是對樣例進行模拟，模拟如下：
2(1,2) 1(1,5) 0(0,1) 第2層 第1次出現在 2(1,2) 密碼為(3+2)%20123=5 第N層無需再找有樓梯的房間
2(1,4) 1(0,3) 0(1,2) 第1層 第1次出現在 1(0,3) 能上樓的房間 找第3個有樓梯的房間 找到2(1,4)
//比如目前房間的訓示牌上寫着2，則按逆時針方向開始嘗試，找到第2個有樓梯的房間
//上面這句很關鍵，請注意，不是連續找2個房間，是找2個有樓梯的房間。
//該題需開一個結構體的二維數組，存儲房間資訊
//該題還需開一個二維數組，逆時針指向有樓梯的房間的序号。
//看了資料範圍，二維數組不會爆記憶體
//采用模運算，不會逾時
//樣例通過，送出0分，全WA。2019-1-23 20:40
//利用https://www.luogu.org/discuss/show/23296中的資料，進行跟蹤
5 4
1 5
1 8
0 5
1 6
0 7
1 65
1 4
0 56
1 8
1 7
1 9
0 11
1 15
1 78
1 98
1 87
1 54
0 45
1 56
1 44
2
153
//b[i][]數組存儲無誤
//怎麼查都查不出，又讀了一遍題目，才發現“如果目前房間本身就有樓梯通向上層，該房間作為第一個有樓梯的房間。”
//題意了解有誤啊，誤以為，上到的這個房間有樓梯，就可以直接到達上一層，其實不是，還需要再找多個房間。
//else{//看題，沒抓住題意，導緻該else功能的缺失。
//修改，送出0分，全WA。2019-1-23 21:35
//将 近1年前AC的代碼，調出來，對比了測試資料的輸出情況，才發現
//now變量指的是在b[i][]中的位置，而不是在q[i][]中的位置。
//修改，送出AC。2019-1-23 22:02
//該題是道 純模拟的題，難在 所有房間， 有樓梯的房間 之間的轉換，如本人編寫的now變量的意義。
//難得，近1年前一次編寫成功，而今，卻反複編寫，卻WA。
//上述資料，執行過程如下：
i=1 start=0 ans=5
i=2 start=1 ans=12
i=3 start=1 ans=19
i=4 start=2 ans=97
i=5 start=3 ans=153
153
//以下為AC代碼。
#include <stdio.h>
#define mod 20123
struct node{
int have,num;
}q[10010][105];
int b[10010][105],N,M,ans=0,start;
int main(){
int i,j,now;
scanf("%d%d",&N,&M);
for(i=1;i<=N;i++){
b[i][103]=0;//用來存儲，有樓梯的房間數
for(j=0;j<M;j++){
scanf("%d %d",&q[i][j].have,&q[i][j].num);
if(q[i][j].have)b[i][b[i][103]++]=j;
}
}
scanf("%d",&start);
for(i=1;i<=N;i++){
ans=(ans+q[i][start].num)%mod;
if(!q[i][start].have){
//找到無樓梯房間之前的第1個有樓梯房間
if(start<b[i][0])now=b[i][103]-1;//此處寫成now=b[i][b[i][103]-1];//無樓梯房間在所有有樓梯房間的在最開始
else if(start>b[i][b[i][103]-1])now=b[i][103]-1;//此處寫成now=b[i][b[i][103]-1];//無樓梯房間在所有有樓梯房間的最後面
else{//無樓梯房間在所有有樓梯房間的中間
for(j=0;j<b[i][103];j++)
if(b[i][j]<start&&start<b[i][j+1]){
now=j;//此處寫成now=b[i][j];
break;
}
}
now=(now+q[i][start].num)%b[i][103];//得到房間序号，在b[i][]中的位置
start=b[i][now];
}else{//看題，沒抓住題意，導緻該else功能的缺失。
for(j=0;j<b[i][103];j++)//此功能後來添加
if(start==b[i][j]){
now=j;
break;
}
now=(now+q[i][start].num-1)%b[i][103];
start=b[i][now];
}
}
printf("%d\n",ans);
return 0;
}
hash
10.方程的解數
//1735 方程的解數
//NOI 2001 共6題
//線上測評位址http://codevs.cn/problem/1735/
//哈希表為什麼要模以素數而非合數，此文講得非常棒https://blog.csdn.net/zhishengqianjun/article/details/79087525
//哈希表解決此題的思路，該文講得很好https://blog.csdn.net/fisher_jiang/article/details/667059
//哈希表早就習得，應用是第一次，甚是高興，理論變現實。
//因計算過程中的資料達到2^31，故采用桶排序，要爆記憶體，隻能采用不爆記憶體的數組存儲
//其中就會遇到沖突，哈希表的算法就十分有用了，
//關鍵有2個函數，一個是定位在數組中的位置，一個是将元素插入數組
//一個比較大的質數4000037,先程式設計簡單的驗證，是否質數
//有個問題，要說明，哈希表中，絕對值相等的正負數，存儲位置不一樣
//突然發現，英語很重要，是不是要把《新概念英語》背起來呢。
//樣例通過，送出AC。2019-2-2 12:07
//該題收獲，掌握了哈希表的寫法。
#include <stdio.h>
#include <string.h>
#define mod 4000037
#define LL long long
int n,m,k[10],p[10],mid;
int amount[mod],used[mod],ans[mod];
LL cnt=0;
int locate(int x){//隻找不改。
int pos;
pos=(mod+x%mod)%mod;//此處寫成pos=(x+x%mod)%mod;，拔低了水準//x為負數，x為正數，均可處理，時間複雜度為O(1)，處理出來的結果為非負數
while(used[pos]&&ans[pos]!=x){//沖突處理,該處已被占用，且不等于x
pos=(pos+1)%mod;
}//跳出循環，要麼該處沒被占用；要麼該處已被占用，存儲的是數x
return pos;
}
void insert(int x){
int pos;
pos=locate(x);
if(used[pos]&&ans[pos]==x)amount[pos]++;//該處已被占用，存儲的是數x
else used[pos]=1,ans[pos]=x,amount[pos]++;//該處沒被占用; 代碼雖然備援，但是易懂，就不精簡了
}
LL quick_pow(int a,int b){
LL ans=1;
while(b){
if(b&1)ans*=a;
a*=a;
b>>=1;
}
return ans;
}
void dfs_left(int step,int sum){//1->mid
int i;
if(step==mid+1){
insert(sum);
return ;
}
for(i=1;i<=m;i++)
dfs_left(step+1,sum+k[step]*quick_pow(i,p[step]));
}
void dfs_right(int step,int sum){//mid+1->n
int i,pos;
if(step+mid==n+1){//此處寫成 if(step==n+1)
pos=locate(-sum);// 右邊結果等于左邊結果的相反數
if(used[pos]&&ans[pos]==-sum)cnt+=amount[pos];
return ;
}
for(i=1;i<=m;i++)
dfs_right(step+1,sum+k[step+mid]*quick_pow(i,p[step+mid]));
}
int main(){
int i;
memset(ans,0,sizeof(ans)),memset(amount,0,sizeof(amount)),memset(used,0,sizeof(used));
scanf("%d%d",&n,&m);
mid=n/2;
for(i=1;i<=n;i++)scanf("%d%d",&k[i],&p[i]);
dfs_left(1,0);
dfs_right(1,0);
printf("%lld\n",cnt);
return 0;
}
//驗證4000037是質數的代碼如下
#include <stdio.h>
#define mod 4000037
int main(){
int i;
for(i=2;i*i<=mod;i++)
if(mod%i==0)printf("No\n");
printf("Yes\n");
return 0;
}
//1735 方程的解數
//NOI 2001 共6題
//線上測評位址http://codevs.cn/problem/1735/
//第一直覺 深搜dfs+剪枝，那點分數應該可以
//指數的p次方，沒說明範圍，為了減少耗時，決定采用快速幂
//為了盡可能的避免int溢出，決定采用long long
//用兩個結構體，一個存非負系數，另一個存負系數
//還好在int範圍内測試了2^31=-2147483648,2^31-1=2147483647
//核心，計算非負的絕對值，計算負的絕對值，比較是否相等，相等即為一種解。
//樣例通過，送出30分，測試點1,5-10TLE，目前盡力了。2019-2-1 16:13
//以下為30分代碼。
#include <stdio.h>
#include <string.h>
#define LL long long
int n,m,cnt_b=0,cnt_c=0;
LL cnt=0;
struct node{
LL k,p;
}b[10],c[10];
LL quick_pow(LL a,LL n){//快速幂
LL ans=1;
while(n){
if(n&1)ans*=a;//此處寫成 if(n&2)ans*=a;
a*=a;
n/=2;
}
return ans;
}
void dfs_c(int step,LL sum1,LL sum2){
int i;
if(sum2>=((1<<31)-1))return;
if(sum2>sum1)return;
if(step==cnt_c+1&&sum1==sum2){
cnt++;
return ;
}
if(step==cnt_c+1)return;//漏了此功能，跟蹤程式後才發現。此句很重要，足足耽擱了30分鐘
for(i=1;i<=m;i++)
dfs_c(step+1,sum1,sum2+c[step].k*quick_pow(i,c[step].p));
}
void dfs_b(int step,LL sum){
int i;
if(sum>=((1<<31)-1))return;
if(step==cnt_b+1){
dfs_c(1,sum,0);
return;
}
for(i=1;i<=m;i++)
dfs_b(step+1,sum+b[step].k*quick_pow(i,b[step].p));
}
int main(){
int i;
LL k,p;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++){
scanf("%lld%lld",&k,&p);
if(k>=0)cnt_b++,b[cnt_b].k=k,b[cnt_b].p=p;
else cnt_c++,c[cnt_c].k=-k,c[cnt_c].p=p;//此處寫成else cnt_c++,b[cnt_c].k=k,b[cnt_c].p=p;跟蹤了程式才查出
}
dfs_b(1,0);
printf("%lld\n",cnt);
return 0;
}
數論
11.數列
//P1062 數列
//NOIP 2006 普及組 第4題 共4題
//線上測評位址https://www.luogu.org/problemnew/show/P1062
//第1直覺，堆+深搜dfs，但是感覺不順手，尋求它法
//轉換成進制，隻需系數<=1即可，否則不符合要求，一個想法掠過
//辦法是好辦法，就是擔心逾時，不過，很好編寫，50分絕對有信心
//程式很快編好，樣例通過，開始測試極端情況
//3 1000 29430 很快
//4 1000 349248 很快
//5 1000沒有輸出，果斷将最大值開到10^7 結果為2440750 很快
//6 1000沒有輸出，果斷将最大值開到10^8 結果為12091896 很快
//7 1000 結果為47076750 有些卡頓，但1s能過
//8 1000沒有輸出，果斷将最大值開到10^9 沒有輸出 有些卡頓，到頭了，
//程式需要修改，int需改成long long
//8 1000 将最大值開到10^10 結果為 153387520 明顯示卡頓，1s過不了
//該算法的極限到了，送出40分，測試點5-10TLE。2019-1-30 18:59
//以下為40分代碼。
//突然想到，該題在考察二進制
//第1個數 1
//第2個數 10
//第3個數 11
//第4個數 100
//第5個數 101
//第6個數 110
//第7個數 111
//該題迎刃而解，N轉換成2進制的
//N=1000,對應2進制 1111101000
//迅速将stack[100],改成stack[20]
//編好後，馬上測試8 1000又快又準，
//測試15 1000，秒出41189262750
//送出AC。2019-1-30 20:55
//完全獨立想出，沒有任何提示
//看來，看了兩集《單挑荒野》還是有收獲的，看好後，突然就想到了上述解法。
#include <stdio.h>
#define LL long long
int k,N,stack[20],top=0;
LL ans=0;
void to2(int x){//N轉2進制
while(x){
stack[++top]=x%2;
x/=2;
}
}
int main(){
int i;
scanf("%d%d",&k,&N);
to2(N);
for(i=top;i>=1;i--){//k進制轉10進制
ans*=k;
ans+=stack[i];
}
printf("%lld\n",ans);
return 0;
}
//P1062 數列
//NOIP 2006 普及組 第4題 共4題
//線上測評位址https://www.luogu.org/problemnew/show/P1062
//第1直覺，堆+深搜dfs，但是感覺不順手，尋求它法
//轉換成進制，隻需系數<=1即可，否則不符合要求，一個想法掠過
//辦法是好辦法，就是擔心逾時，不過，很好編寫，50分絕對有信心
//程式很快編好，樣例通過，開始測試極端情況
//3 1000 29430 很快
//4 1000 349248 很快
//5 1000沒有輸出，果斷将最大值開到10^7 結果為2440750 很快
//6 1000沒有輸出，果斷将最大值開到10^8 結果為12091896 很快
//7 1000 結果為47076750 有些卡頓，但1s能過
//8 1000沒有輸出，果斷将最大值開到10^9 沒有輸出 有些卡頓，到頭了，
//程式需要修改，int需改成long long
//8 1000 将最大值開到10^10 結果為 153387520 明顯示卡頓，1s過不了
//該算法的極限到了，送出40分，測試點5-10TLE。2019-1-30 18:59
//以下為40分代碼。
#include <stdio.h>
#define LL long long
int k,N,cnt=0;
int judge(LL x){//0不符，1符合要求
while(x){
if(x%k>1)return 0;//系數 大于 1
x/=k;
}
return 1;
}
int main(){
LL i;
scanf("%d%d",&k,&N);
for(i=1;i<=10000000000LL;i++){// 10000000000LL此句寫得不錯
if(judge(i))cnt++;
if(cnt==N){
printf("%lld\n",i);
break;
}
}
return 0;
}
12.同餘方程
//P1082 同餘方程
//NOIP 2012 提高組 day2 第1題 day2 共3題
//線上測評位址https://www.luogu.org/problemnew/show/P1082
//ax+by=1,gcd(a,b)=1,肯定成立，因，輸入資料保證一定有解
//擴充歐幾裡得算法exgcd
//因資料a,b最大值2000000000,采用long long比較穩妥
//解決該題的過程，就是 擴充歐幾裡得算法 重新推導的過程
//獨立推導完成，沒有借助任何資料。
//樣例通過，送出AC。2019-1-30 16:53
#include <stdio.h>
int exgcd(int a,int b,int *x,int *y){
int d,t;
if(b==0){
*x=1,*y=0;
return a;
}
d=exgcd(b,a%b,x,y);
t=*x,*x=*y,*y=t-a/b**y;
return d;
}
int main(){
int a,b,x,y;
scanf("%d%d",&a,&b);
exgcd(a,b,&x,&y);
x=(b+x%b)%b;
printf("%d\n",x);
return 0;
}
13.多項式系數
//P1313 計算系數
//NOIP 2011 提高組 第2天 第1題 第2天 共3題
//線上測評位址https://www.luogu.org/problemnew/show/P1313
//翻看本人之前代碼，竟有逆元之說，決定停下腳步，把這些遺忘的知識拾起。
//通過此文https://www.cnblogs.com/rir1715/p/7748054.html瞬間搞懂了，逆元的計算公式。
//逆元有一個要素，模運算的數字需是質數。其中用到了費馬小定理
//第1步，先驗證10007是質數
//發現是質數，可以開始乘法逆元
//有乘法逆元的地方，就有快速幂
//樣例通過，送出AC。2019-1-30 9:57
//乘法逆元有些感覺了。
#include <stdio.h>
#define mod 10007
#define LL long long
LL quick_pow(int x,int n){
LL ans=1;
while(n){
if(n&1)ans=(ans*x)%mod;
x=(x*x)%mod;
n/=2;
}
return ans;
}
int main(){
int i,a,b,k,n,m;
LL c=1,A=1,B=1,d=1,ans;
scanf("%d%d%d%d%d",&a,&b,&k,&n,&m);
for(i=k;i>=k-n+1;i--)c=(c*i)%mod;
for(i=n;i>=1;i--)d=(d*i)%mod;
c=(c*quick_pow(d,mod-2))%mod;//乘法逆元
for(i=1;i<=n;i++)A=(A*a)%mod;
for(i=1;i<=m;i++)B=(B*b)%mod;
ans=(c*A*B)%mod;
printf("%lld\n",ans);
}
//P1313 計算系數
//NOIP 2011 提高組 第2天 第1題 第2天 共3題
//線上測評位址https://www.luogu.org/problemnew/show/P1313
//通項公式C(k,n)(ax)^n(by)^(k-n)
//楊輝三角即可解決 C(k,n)
//因對10007取模，int不會溢出
//測算了10007*1000000=10^10，int溢出，還需long long
//for(i=0;i<=k;i++)c[i][i]=c[i][0]=1;//此處寫成 for(i=0;i<=k;k++)c[i][i]=c[i][0]=1;查了20分鐘
//測試的時候，就覺得奇怪，怎麼會超1s，原來是筆誤引出的。
//樣例通過，送出50分，測試點2,3,6-8 WA.2019-1-30 8:38
//怎麼可能，重新讀題，對特殊情況，進行了解，沒問題啊
//再讀代碼，又發現一處筆誤
//for(i=1;i<=m;i++)B=(B*b)%mod;//此處寫成 for(i=1;i<=m;i++)B=(B*a)%mod; 導緻送出50分
//修改，送出AC，2019-1-30 8:44
//送出前，還是要多測試，筆誤之類的，完全能在測試中發現，這樣，送出，更有信心。
#include <stdio.h>
#define LL long long
#define mod 10007
int a,b,k,n,m,c[1010][1010];
LL A=1,B=1,ans;
int main(){
int i,j;
scanf("%d%d%d%d%d",&a,&b,&k,&n,&m);
for(i=0;i<=k;i++)c[i][i]=c[i][0]=1;//此處寫成 for(i=0;i<=k;k++)c[i][i]=c[i][0]=1;查了20分鐘
for(i=2;i<=k;i++)//此處寫成 for(i=1;i<=k;i++)
for(j=1;j<i;j++)
c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
for(i=1;i<=n;i++)A=(A*a)%mod;
for(i=1;i<=m;i++)B=(B*b)%mod;//此處寫成 for(i=1;i<=m;i++)B=(B*a)%mod; 導緻送出50分
ans=(c[k][n]*A*B)%mod;
printf("%lld\n",ans);
return 0;
}
dfs
14.選數
//P1036 選數
//NOIP 2002 普及組 第2題 共4題
//線上測評位址https://www.luogu.org/problemnew/show/P1036
//深搜dfs即可解決。
//最大和，5000000*20=10^8,int不會溢出
//樣例通過，送出AC。2019-1-22 19:47
//翻看代碼，比2年前，寫得棒多了。
#include <stdio.h>
#define maxn 25
int a[maxn],n,k,cnt=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 start,int sum){
int i;
if(step==k+1){
if(isPrime(sum))cnt++;
return ;
}
for(i=start;i<=n;i++)
dfs(step+1,i+1,sum+a[i]);//此處寫成i+1甚為精妙
}
int main(){
int i;
scanf("%d%d",&n,&k);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
dfs(1,1,0);
printf("%d\n",cnt);
return 0;
}
高精度
15.回文數
//P1015 回文數
//NOIP 1999 提高組 第2題 共4題
//線上測評位址https://www.luogu.org/problemnew/show/P1015
//測算int或是long long 是否會溢出
//98+89=187 187+781=968 968+869=1837 1837+7381=9218
//9218+8129=17347 17347+74371=91718 91718+81719=173437
//173437+734371=907808 907808+808709=1716517
//1716517+7156171=872688
//受不了了，還是編個程式測試了再說
//測試98，int沒有溢出，測試99，int溢出
//想過用long long，但該題已經沒有意義，因為是設計N進制
//改成字元串，省時省力，用高精度加
//該題，還需特判，如，輸入的數，本身就是回文
//讀題，發現進制數M(100位之内)，看成了100之内，還好及時發現
//因涉及16進制，故不采用int
//再想想，加法計算不好處理，決定還是從char a[]回歸到int a[]
//樣例通過，送出25分，測試點1,2,4 WA
//這麼簡單的題，怎麼會錯，仔細想了想，做該題過程中，被打斷了四次
//錯也難怪，錯了之後，馬上想到，是M進制，編的過程中，寫成了10進制
//馬上修改，送出75分，測試點2 WA。
//翻看了https://www.luogu.org/discuss/show/53147讨論，輸入資料也可以是16進制，昏倒
//缺失沒考慮到
//修改，送出AC。2019-1-24
#include <stdio.h>
#include <string.h>
#define maxn 1000000
int N;
int a[maxn],b[maxn],c[maxn];
char s[maxn];
int judge(int *s){
int i;
for(i=1;i<=s[0]/2;i++)
if(s[i]!=s[s[0]-i+1])
return 0;//非回文
return 1;//回文
}
void reverse(int *x,int *y){
int i;
y[0]=x[0];
for(i=1;i<=x[0];i++)y[x[0]-i+1]=x[i];
}
void add(int *x,int *y){
int i;
memset(c,0,sizeof(c));
c[0]=x[0];
for(i=1;i<=c[0];i++){
c[i]+=x[i]+y[i];
c[i+1]+=c[i]/N;//此處寫成 c[i+1]+=c[i]/10;
c[i]%=N;//此處寫成c[i]%=10;
}
if(c[i])c[0]=i;
memcpy(a,c,sizeof(c));
}
int main(){
int i;
scanf("%d%s",&N,s+1);
a[0]=strlen(s+1);
for(i=1;i<=a[0];i++)
if('A'<=s[i]&&s[i]<='F')a[i]=s[i]-'A'+10;
else if('a'<=s[i]&&s[i]<='f')a[i]=s[i]-'a'+10;
else a[i]=s[i]-'0';//隻考慮了0-9
if(judge(a))printf("STEP=0\n");//特判
else{
for(i=1;i<=30;i++){
reverse(a,b);
add(a,b);
if(judge(a)){
printf("STEP=%d\n",i);
break;
}
}
if(i==30+1)printf("Impossible!\n");
}
return 0;
}
模拟
16.現在幾點鐘
//1063: 現在幾點鐘?
//線上測評位址http://218.5.5.242:9018/JudgeOnline/problem.php?id=1063
//問題中，表述的東西比較多
//按先特判，再一般情形，程式會比較容易編寫。
//測試了幾組時間資料的讀取
//1:00 讀入1 0
//1:03 讀入1 3
//開始進行特判的處理
//突然發現，英語沒學好的，這個題目難以做好，有一堆單詞要獨立寫出
//編寫一個時間，測試一個時間
//問題中給的資料全部通過，送出AC。眼淚都要掉下來了，生怕英文單詞寫錯
//基本可判定，問題中給出的資料，就是該問題的測試點。2019-1-22 21:05
//該題，主要在練，if else + 字元串簡單處理。
#include <stdio.h>
#include <string.h>
int h,m;
char num[][20]={"","one","two","three","four","five","six","seven","eight","nine","ten","eleven","twelve","thirteen","fourteen","fifteen","sixteen","seventeen","eighteen","nineteen","twenty","thirty","forty"};
char ten[][20]={"","","twenty","thirty","forty"};
int main(){
char s[20];
scanf("%d:%d",&h,&m);
if(m==0){//5:00 Five o'clock
strcpy(s,num[h]);
s[0]=s[0]-'a'+'A';
printf("%s o'clock\n",s);
}else if(m==15){//5:15 Quarter past five
printf("Quarter past %s\n",num[h]);
}else if(m==45){//5:45 Quarter to six
if(h==12)h=1;//要小心12 與 1的關系
else h+=1;
printf("Quarter to %s\n",num[h]);
}else if(m<45){
strcpy(s,num[h]);
s[0]=s[0]-'a'+'A';
printf("%s ",s);
if(m<=20)printf("%s",num[m]);//10:10 Ten ten
else{//9:22 Nine twenty-two 2:30 Two thirty 6:40 Six forty
printf("%s",ten[m/10]);
if(m%10)printf("-%s",num[m%10]);
}
}else if(m>45){//8:47 Thirteen to nine 12:47 Thirteen to one (American time: 1:00 follows 12:00)
strcpy(s,num[60-m]);
s[0]=s[0]-'a'+'A';
printf("%s",s);
if(h==12)h=1;//要小心12 與 1的關系
else h+=1;
printf(" to %s",num[h]);
}
return 0;
}
17.選擇客棧
//P1311 選擇客棧
//NOIP 2011 提高組 day1 第2題 day1 共3題
//線上測評位址https://www.luogu.org/problemnew/show/P1311
//有O(n)的算法，那麼要好好學習
//https://www.luogu.org/problemnew/solution/P1311的作者: ShawnZhou可以看看
//以下是改進，更易于了解。
//思路，有些類似 歸并排序求逆序對，最長上升子序列。都是以i為結尾的情況分析。
//樣例通過，送出AC。2019-1-31 22:54
#include <stdio.h>
#include <string.h>
#define LL long long
#define maxn 55
int cnt[maxn],last[maxn],sum[maxn];//cnt[j]j顔色的數量 last[j] j顔色曆此次最近一次出現的位置 sum[j] j顔色在now位置之前(包含)出現的次數
int main(){
int i,now=0,color,price,n,k,p;
LL ans=0;
scanf("%d%d%d",&n,&k,&p);
memset(cnt,0,sizeof(cnt)),memset(last,0,sizeof(last));
for(i=1;i<=n;i++){
scanf("%d%d",&color,&price);
if(price<=p)now=i;//更新最新喝咖啡客棧位置
if(now>=last[color])sum[color]=cnt[color];//在now之前(包含)color客棧的數量
ans+=sum[color];//以客棧i為結尾的符合條件的客棧的個數，有點象 歸并排序求逆序對
last[color]=i;//更新color客棧最新位置
cnt[color]++;
}
printf("%lld\n",ans);
return 0;
}
//P1311 選擇客棧
//NOIP 2011 提高組 day1 第2題 day1 共3題
//線上測評位址https://www.luogu.org/problemnew/show/P1311
//因n=200000，算法的時間複雜度，要麼O(n),要麼O(nlogn).
//該題，要得50分，即n=1000,采用O(n^2)的算法，還是比較簡單的
//sum[i][j]以i客棧為結尾j顔色客棧的數量
//該題純模拟+數組的組合知識 即可。
//int可能溢出，考慮用long long
//樣例通過，送出AC。2019-1-31 18:23
//純模拟，算法的時間複雜度O(nk)
//自我感覺，這個算法程式易編出，也不容易出錯。
#include <stdio.h>
#include <string.h>
#define LL long long
int n,k,p,q[200010],color[55],b[200010];//b[i] i位置的顔色
LL sum[200010][55],ans=0;
int main(){
int i,j,c,consume,now;
memset(sum,0,sizeof(sum)),memset(color,0,sizeof(color));
scanf("%d%d%d",&n,&k,&p);
for(i=1;i<=n;i++){//時間複雜度nk,應該能險過
scanf("%d%d",&c,&consume);//此處寫成 scanf("%d%d",&c,consume); 查了會
color[c]++,b[i]=c;
for(j=0;j<k;j++)sum[i][j]=color[j];
q[i]=consume;
}
now=0;
for(i=1;i<=n;i++)
if(q[i]<=p){
for(j=0;j<k;j++)
if(b[i]==j)//最低消費客棧，參與住宿1 2 3(最低消費，參與住宿) 4 5 2*3+2=8
ans+=(sum[i-1][j]-sum[now][j])*(sum[n][j]-sum[i-1][j])+sum[n][j]-sum[i][j];
else//最低消費客棧，不參與住宿 1 2 3(最低消費，不參與住宿) 4 5 2*2=4
ans+=(sum[i-1][j]-sum[now][j])*(sum[n][j]-sum[i-1][j]);
now=i;
}
printf("%lld\n",ans);
return 0;
}
18.機器翻譯
//P1540 機器翻譯
//NOIP 2010 提高組 第1題 共4題
//線上測評位址https://www.luogu.org/problemnew/show/P1540
//隊列
//樣例通過，送出AC。2019-1-23 17:25
//感覺，比起從前，該題變得太輕松了。
#include <stdio.h>
#include <string.h>
#define maxn 1100
int q[maxn],h,t;
int main(){
int m,n,a,i,cnt=0;
memset(q,0,sizeof(q));
scanf("%d%d",&m,&n);
h=t=1;
while(n--){
scanf("%d",&a);
for(i=h;i<t;i++)
if(q[i]==a)break;
if(i==t){//i==t發生在，沒找到該單詞
cnt++;
if(t-h<m)//加入記憶體
q[t]=a,t++;
else//清理記憶體，加入記憶體
h++,q[t]=a,t++;
}
}
printf("%d\n",cnt);
return 0;
}
19.電腦的改良
//P1022 電腦的改良
//NOIP 2000 普及組 第1題 共4題
//線上測評位址https://www.luogu.org/problemnew/show/P1022
//該題有現實意義，有些電腦提供了解方程的功能
//讀完題，沒什麼好思路，純模拟
//字元串讀入，之後進行解析，處理
//測試了，3+-3發現能正确運算，3--3報錯，-3+-3能正确運算，-3--3報錯
//考什麼呢，不過需求來源于生活，首要就是将其解決，再考慮優化
//對樣例進行研究
//6a-5+1=2-2a a=0.750
//6a-5+1=-2a+2 a=0.750
//送出AC。2019-1-31 12:18
//從左往右掃的過程中，找出數字是關鍵，數字之前是符号，數字之後是未知數或等号或符号，等号之前是未知數或數字
//該題純模拟，沒有什麼技巧，不過需注意一些特殊情況。
#include <stdio.h>
#include <string.h>
char s[1000];
int main(){
int i,len,op,d,fm=0,fz=0,right=0;//op為1表示負數，op為0表示正數 fm分母，fz分子
char alpha;
scanf("%s",s);
len=strlen(s);
i=0;
while(i<len){
d=0,op=0;
while('0'<=s[i]&&s[i]<='9'){
if(i-1<0)op=0;
else if(s[i-1]=='+')op=0;
else if(s[i-1]=='=')op=0,right=1;
else if(s[i-1]=='-')op=1;
d*=10,d+=s[i]-'0',i++;
}//數字處理
if('a'<=s[i]&&s[i]<='z'){//未知數及系數處理
alpha=s[i];
if(right==0){
if(d==0)fm+=1;
else if(op==0)fm+=d;
else if(op==1)fm-=d;
}else{
if(d==0)fm-=1;
else if(op==0)fm-=d;
else if(op==1)fm+=d;
}
}else if(right==0){
if(op==0)fz-=d;
else if(op==1)fz+=d;
}else if(right==1){
if(op==0)fz+=d;
else if(op==1)fz-=d;
}
if(s[i]=='=')right=1;//漏了此句，通過測試資料6a-5+1=-2a+2 a=0.750，發現了疏漏
i++;
}
printf("%c=%.3lf\n",alpha,fz*1.0/fm);
return 0;
}
20.分數線劃定
//P1068 分數線劃定
//NOIP 2009 普及組 第2題 共4題
//線上測評位址https://www.luogu.org/problemnew/show/P1068
//排序采用sort函數
//樣例通過，送出，再次遇到Compile Error,爆0
//可憐的windows下的C++編成，頭檔案，缺失，編譯器竟然不提示
//添加頭檔案，送出AC。2019-1-23
//感覺編得比以前輕松，但是C++隐患太大，需到linux環境中，C++編寫，才有保障
#include <cstdio>
#include <algorithm>
#include <cstring>//漏了此頭檔案
using namespace std;
#define maxn 5100
struct node{
int seq,score;
}q[maxn];
int cmp(const struct node &a,const struct node &b){//自大到小
if(a.score==b.score)return a.seq<b.seq;
return a.score>b.score;//此處寫成return a.score<b.score;
}
int main(){
int n,m,i,p,cnt,score;
memset(q,0,sizeof(q));
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)scanf("%d%d",&q[i].seq,&q[i].score);
sort(q+1,q+1+n,cmp);
cnt=p=(int)(m*1.5);
score=q[cnt].score;
while(q[cnt+1].score==score)cnt++;//從p位置開始數
printf("%d %d\n",score,cnt);
for(i=1;i<=cnt;i++)printf("%d %d\n",q[i].seq,q[i].score);
return 0;
}
進制
21.進制轉換
//P1017 進制轉換
//NOIP 2000 第1題 共4題
//線上測評位址https://www.luogu.org/problemnew/show/P1017
//做慣了 正數 正基數，突然遇到了 負基數 正數或負數
//卡頓了很長時間，
//反複對比 正數 正基數，以及 餘數 需小于 負基數的絕對值 ，才基本明白該題中的進制轉換
//-15，-2；15，-2模拟如下
//該題難在，思考出上述模拟過程
//需簡單測試，負數的除模運算。
//-15/-2=7,-15%-2=-1;15/-2=7,15%-2=1
//負數沒法用除模運算，得自己編；正數還能用用
//-15/-2這樣處理15/2=7,商7+1=8,餘數-15-(-2*8)=1
//因輸入是10進制，輸入處理就比較輕松。
//N=0需特判
//在猶豫，16進制列印大寫字母，還是小寫字母，發現樣例4已經給出了結果
//樣例通過，送出AC.2019-1-29 20:06
//為了弄清，棧空間，做了如下測試。
//-32768 -2
//-32768=1000000000000000(base-2)
//32767 -2
//32767=11000000000000011(base-2)
//空間開100足以
//修改，送出AC。2019-1-29 20:10
#include <stdio.h>
int N,R,m,s;//m對應負數N的絕對值，s對應負數R的絕對值
int stack[100],top=0;//開多少位比較合适呢？不要小氣，大氣些，先開10000，具體可編好後測試，測試發現100足以
int main(){
int i;
scanf("%d%d",&N,&R);
printf("%d=",N);
if(N==0){//N=0需特判
printf("0(base%d)\n",R);
return 0;
}
while(N){
if(N<0){
m=-N,s=-R;
if(m%s==0){//能整除
N=m/s;
stack[++top]=0;
}else{//不能整除
stack[++top]=N-(m/s+1)*R;
N=m/s+1;
}
}else{//N>0
stack[++top]=N%R;
N/=R;
}
}
for(i=top;i>=1;i--){
if(stack[i]<10)printf("%d",stack[i]);
else printf("%c",stack[i]-10+'A');
}
printf("(base%d)\n",R);
return 0;
}
枚舉
22.一進制三次方程求解
//P1024 一進制三次方程求解
//NOIP 2001 提高組 第1題 共4題
//線上測評位址https://www.luogu.org/problemnew/show/P1024
//因根的範圍在-100-100之間，精确到小數點後2位 ，隻需計算-100.00-100.00
//為了更精确，計算-100.0000-100.000即可，需算2000000,穩過，綜上所述，該題傻算即可。
//樣例沒通過，重新看了題目，發現4個實數A,B,C,D，之前誤以為是4個整數，還好樣例沒通過，馬上修改
//發現 return fabs(a*x*x*x+b*x*x+c*x+d);//此處寫成 return a*x*x*x+b*x*x+c*x+d;
//應是比較的絕對值
//送出AC。2019-1-24
//對比了該題之前編寫的代碼，發現應試能力有了大大的提高。
#include <stdio.h>
#include <math.h>
#define eps 1e-7
double f(double a,double b,double c,double d,double x){
return fabs(a*x*x*x+b*x*x+c*x+d);//此處寫成 return a*x*x*x+b*x*x+c*x+d;
}
int main(){
int i,cnt=0;
double a,b,c,d,x;
scanf("%lf%lf%lf%lf\n",&a,&b,&c,&d);
for(i=0;i<=2000000;i++){
x=-100+0.0001*i;
if(f(a,b,c,d,x)<=eps){
printf("%.2lf ",x);
cnt++;
if(cnt==3)break;
}
}
return 0;
}
![重走長征路---OI每周刷題記錄---10月20日 2013 AC 10題[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)