9.15——模拟赛
T1 太（洛谷 ——U3348 A2-回文數）
題目描述：
殘存的碎片卻愈加清晰。
好久一段時間，記憶突然停頓了，腦子一片空白。
忘記此刻是何年何月， 甚至忘記自己是誰， 等待太久， 一切都回不到最初的原點。
九年。
相遇，分離，重逢，再…… 從初始到末端。
如傻瓜般虔誠的追隨在你左右。
思路：大模擬,打表找規律
2333 年，在銀河系的某星球上，X 軍團和 Y 軍團正在激烈地作
戰。在戰斗的某一階段，Y 軍團一共派遣了 N 個巨型機器人進攻 X
軍團的陣地，其中第 i 個巨型機器人的裝甲值為 Ai。當一個巨型機器
人的裝甲值減少到 0 或者以下時，這個巨型機器人就被摧毀了。X 軍
團有 M 個激光武器， 其中第 i 個激光武器每秒可以削減一個巨型機器
人 Bi 的裝甲值。激光武器的攻擊是連續的。這種激光武器非常奇怪，
一個激光武器只能攻擊一些特定的敵人。 Y 軍團看到自己的巨型機器
人被 X 軍團一個一個消滅，他們急需下達更多的指令。
輸入描述：
一行 給你一個數 n 表示下達的指令。
輸出描述：
一行 請輸出第 n 個回文數
樣例輸入：
輸入樣例#1：
2333
輸出樣例#1：
1334331
樣例輸出：
輸入樣例#2：
12345678987654321
輸出樣例#2：
23456789876543222234567898765432
提示：
對于 10%的數據 n<=100
對于 20%的數據 n<=100000000
對于 100%的數據 n<=1000000000000000000
?
打表找規律，發現輸入的n，第一位-1，最后一位+1，就是回文數的一半（注意處理進位）
回文數長度為1的有9個，len==2的有9 的，依次 90 90 900 900 9000 9000.。。。
可以根據n判斷出回文數的長度奇偶，再判斷輸出的數。。。
1 #include <cstring> 2 #include <cstdio> 3 4 #define LL long long 5 6 LL a,len; 7 int beg=1,cnt,num[50]; 8 9 inline void Pre() 10 { 11 LL tot=9,tmp=9; len=1; 12 for(int i=1; tot<=a; ++len,++i) 13 if(i==2) i=0,tmp*=10,tot+=tmp; 14 else tot+=tmp; 15 for(; a; a/=10) 16 num[++cnt]=a%10; 17 num[beg]++; num[cnt]--; 18 for(int i=1; num[i]==10; ) 19 num[i++]=0,num[i]++; 20 for(; !num[cnt]; --cnt) 21 if(!num[cnt-1]) num[cnt-1]=9; 22 } 23 24 int Presist() 25 { 26 // freopen("hwc.in","r",stdin); 27 // freopen("hwc.out","w",stdout); 28 scanf("%lld",&a); Pre(); 29 if(len&1) 30 { 31 for(int i=cnt; i; --i) printf("%d",num[i]); 32 for(int i=2; i<=cnt; ++i) printf("%d",num[i]); 33 } 34 else 35 { 36 for(int i=cnt; i; --i) printf("%d",num[i]); 37 for(int i=1; i<=cnt; ++i) printf("%d",num[i]); 38 } 39 return 0; 40 } 41 42 int Aptal=Presist(); 43 int main(){;} AC?
?
T2?妃 （洛谷——P2905 [USACO08OPEN]農場危機Crisis on the Farm）
題目描述：
回憶的章節錯亂不堪，想要收拾那些畫面用來重溫，卻顯得七零八亂。
整個人是麻木的，記憶也跟著蒼白。
曾留下太多太深的足跡在心里。
刻意隱瞞，隱藏，隱忍著……
用近乎笨拙的方式隱身荒蕪的背后，一直在原地徘徊。
決絕的用極端的方式否定了一切的傷痕和不舍， 清楚的聽見自己心碎的聲音。
一次次對靈魂華麗的自殘，壯觀而且荒謬。
我想我還是做錯了，一味強求，不想離開你。
眾所周知，三校區有一項優雅的大課間活動——廣場舞。廣
場舞在以前是十分好跳的，同學們只要隨著音樂翩翩起舞即可。但是
三區校長為了增加廣場舞的趣味性和可觀性， 勒令同學們摞成一摞跳
操。同學們礙于各班班長的淫威只得同意了，同學們在跳操時是這樣
紙的，30 個人摞成一摞(因為學校人數太少了，(*^__^*) )，摞成了
n 摞：
校長會偷偷的窩在小黑屋里，放各種顏色的煙花來指揮跳舞。
校長最多可以燃放 30 個煙花，煙花有四種顏色，分別可以指揮所有
的同學向東，西，南，北各移動一個格。但是這樣跳操太累了，同學
們都想偷懶，當一摞同學最下面的同學移動到教學樓時，這摞同學最
上面的學生會跳到教學樓頂層，如下圖：
思路：惡心的動歸具體見代碼。
同學們想要盡可能多的偷懶，于是找到了你，總校后勤煙花
爆竹管制處處長。
因為校長的煙花都是由你提供的，而校長只會按照你提供的
煙花的順序去燃放煙花，請你給出最多可以有幾名同學偷懶，和此時
燃放煙花的順序。順序用 E，W,S，N 表示指揮東西南北各種不同顏色
的煙花。若有多個相同的，輸出字典序最小的。
輸入描述：
第 1 行 3 個整數 n，m，k，描述同學摞成了幾摞，教學樓的個
數，校長可燃放的煙花的個數。
第 2 到 1+n 行每行兩個整數 x，y，描述 n 摞同學開始時的坐
標。
第 n+2 到 n+m+1 行每行兩個整數 x，y，描述 m 個教學樓的坐
標。
輸出描述：
兩行。
第一行 ：最多能偷懶的學生的個數。
第二行 ：此時燃放煙花的方案。
樣例輸入：
3 6 3
3 4
6 2
5 7
8 2
9 2
6 4
5 4
6 7
8 7
樣例輸出：
6
EEE
提示：
10%的數據，n<=1000,m<=1000,k<=5
40%的數據，n<=1000,m<=1000,k<=10
70%的數據，n<=1000;m<=1000;k<=20
100%的數據，n<=1000,m<=1000,k<=30，0<=x<=10000,0<=y<=10000
?
?f[k][i][j]表示走k步，到(i,j)的最大價值，
加31預防出現負坐標
1 #include <cstdlib> 2 #include <cstdio> 3 4 const int N(1005); 5 inline void read(int &x) 6 { 7 x=0; register char ch=getchar(); 8 for(; ch>'9'||ch<'0'; ) ch=getchar(); 9 for(; ch>='0'&&ch<='9'; ch=getchar()) x=x*10+ch-'0'; 10 } 11 12 int n,m,k,ans; 13 int fx[4]={1,0,0,-1}; 14 int fy[4]={0,1,-1,0}; 15 int f[35][65][65],get[65][65]; 16 17 char step[35][65][65]; 18 char ch[4]={'W','S','N','E'}; 19 20 struct life { 21 int x,y; 22 }cow[N],grass[N]; 23 24 #define max(a,b) (a>b ?a :b) 25 26 int Presist() 27 { 28 read(n),read(m),read(k); 29 for(int i=1; i<=n; ++i) 30 read(cow[i].x),read(cow[i].y); 31 for(int i=1; i<=m; ++i) 32 read(grass[i].x),read(grass[i].y); 33 for(int i=1; i<=n; ++i) 34 for(int j=1; j<=m; ++j) 35 { 36 int dx=cow[i].x-grass[j].x; 37 int dy=cow[i].y-grass[j].y; 38 if(abs(dx)+abs(dy)<=30) get[dx+31][dy+31]++; 39 } 40 for(int t=0; t<=k; ++t) 41 for(int i=0; i<=62; ++i) 42 for(int j=0; j<=62; ++j) 43 { 44 f[t][i][j]=-0x3f3f3f3f; 45 step[t][i][j]='Z'; 46 } 47 f[0][31][31]=get[31][31]; 48 for(int t=1; t<=k; ++t) 49 for(int i=1; i<=62; ++i) 50 for(int j=1; j<=62; ++j) 51 f[t][i][j]=get[i][j]+max(max(f[t-1][i+1][j],f[t-1][i][j-1]), 52 max(f[t-1][i-1][j],f[t-1][i][j+1])); 53 for(int i=1; i<=62; ++i) 54 for(int j=1; j<=62; ++j) 55 ans=max(ans,f[k][i][j]); 56 printf("%d\n",ans); 57 for(int i=1; i<=62; ++i) 58 for(int j=1; j<=62; ++j) 59 if(ans==f[k][i][j]) step[k][i][j]='A'; 60 for(int t=k-1; t>=0; t--) 61 for(int i=1; i<=61; ++i) 62 for(int j=1; j<=61; ++j) 63 for(int h=0; h<4; ++h) 64 { 65 int xx=i+fx[h],yy=j+fy[h]; 66 if(f[t][i][j]+get[xx][yy]==f[t+1][xx][yy]&&step[t+1][xx][yy]<'Z') 67 step[t][i][j]=ch[h]; 68 } 69 for(int x=31,y=31,t=0; t<k; ++t) 70 { 71 printf("%c",step[t][x][y]); 72 if(step[t][x][y]=='N') y--; 73 else if(step[t][x][y]=='S') y++; 74 else if(step[t][x][y]=='W') x++; 75 else if(step[t][x][y]=='E') x--; 76 } 77 return 0; 78 } 79 80 int Aptal=Presist(); 81 int main(){;} AC?
?
T3?糖 ?（洛谷——P2868 [USACO07DEC]觀光奶牛Sightseeing Cows）
題目描述：
還是忘不了。
關于你的好與不好。
分分合合，早已成為習慣。
偏執的如同我的性格般執拗。
什么事都不做，安靜的蜷縮在被窩里，細數自己的心碎與莫落。
最初的最初。
最后的最后。
Xxy 每天都奮斗在跳樓梯的第一線， 所以回宿舍后感到又累又
餓，很快陷入了夢鄉。在夢中，xxy 進入了一個巨大的城堡。
這個題從葉子節點去算的話顯然很困難，所以我們可以從 xx
所在的兩個點開始倒著搞。 min 和 man 記錄每個節點最多和最少有
多少個糖果才能讓 xx 恰好吃到 k 只。然后，分別以這兩個點為根節
點，深搜一下求出所有的 min 和 man。
接著，二分答案，求一下對于每個節點,g 群糖果中符合條件的糖果
的群數。最后，群數*k 即為所求。
Xxy 驚訝的發現，這座城堡有 n 個房間和 m 條走廊，走廊非常
窄，只能單向通行。Xxy 驚訝的發現在每個房間里都有一個魔法陣，
魔法陣可以召喚魔法糖果，每個房間有且只有一個魔法糖果。每個魔
法糖果都有一個飽腹值， xxy 吃下糖果，就會增加飽腹值，不那么餓。
與吃糖果相反的是，xxy 需要穿越走廊才能吃到糖果，而每個走廊又
有一定的疲憊值。Xxy 想在吃完糖果后返回出發點。
Xxy 現在非常的饑餓， 所以她想吃到盡量多的糖果。 但是， xxy
也非常的累，所以她不想去浪費時間走更多的路。所以 xxy 希望在平
均單位時間里，獲得的飽腹值盡可能的大。請問 xxy 能得到的最大平
均飽腹值是幾？（因為 xxy 太餓了，所以他至少要吃掉 2 顆糖果）
輸入描述：
第一行：輸入 n，m，分別表示城堡中房間的數量，和走廊的
數量。
第二行：輸入 n 個數 f，表示從 1 到 n 號房間內，每個房間里
糖果能提供的飽腹值。
接下來 m 行，每行輸入三個數 x，y，z,表示房間 x 與 y 之間
有走廊相連通。走完這條走廊的疲憊之為 z。
輸出描述：
一行，一個數 ans 表示 xxy 能得到的最大平均飽腹值，結果
保留兩位小數。
樣例輸入：
5 7
30
10
10
5
10
1 2 3
2 3 2
3 4 5
3 5 2
4 5 5
5 1 3
5 2 2
樣例輸出：
6.00
提示：
對于 100%數據:2≤n≤1000， 2≤m≤5000， 1≤x,y≤n,1≤f,z≤1000。
?
設奶牛經過val[1],val[2],val[3],val[4]（點1 2 3 4），遍w[1],w[2],w[3],w[4]（1->2,w1,,,,2->3,w2......3->4,w3.....4->1,w4）
二分一個ans，則ans=(val[1]+val[2]+val[3]+val[4]) / (w[1]+w[2]+w[3]+w[4])---->>>
0=ans*w[1]-val[2]+ans*w[2]-val[3]+ans*w[3]-val[4]+ans*w[4]-val[1]
可以以ans*邊權-（連出）點權作為最短路的邊，判斷是否存在負環驗證ans是否最優
DFS判負環比BFS快得多
1 #include <cstring> 2 #include <cstdio> 3 #include <queue> 4 5 const int INF(0x3f3f3f3f); 6 const int N(12001+5); 7 const int M(10626+5); 8 inline void read(int &x) 9 { 10 x=0; register char ch=getchar(); 11 for(; ch>'9'||ch<'0'; ) ch=getchar(); 12 for(; ch>='0'&&ch<='9'; ch=getchar()) x=x*10+ch-'0'; 13 } 14 15 int n,m,val[N]; 16 int head[N],had[N],sum,sumedge; 17 struct Edge { 18 int v,next; 19 double w; 20 Edge(int v=0,int next=0,double w=0.0):v(v),next(next),w(w){} 21 }edge[M],e[M]; 22 inline void ins(int u,int v,double w) 23 { 24 edge[++sumedge]=Edge(v,head[u],w); 25 head[u]=sumedge; 26 } 27 inline void insert(int u,int v,double w) 28 { 29 e[++sum]=Edge(v,had[u],w); had[u]=sum; 30 } 31 /* 32 int cnt[N]; 33 bool inq[N]; 34 double dis[N]; 35 36 bool SPFA(int s) 37 { 38 std::queue<int>que; 39 memset(cnt,0,sizeof(cnt)); 40 memset(inq,0,sizeof(inq)); 41 memset(dis,127/3,sizeof(dis)); 42 que.push(s); dis[s]=0; cnt[s]++; 43 for(int u,v; !que.empty(); ) 44 { 45 u=que.front(); que.pop(); inq[u]=0; 46 for(int i=head[u]; i; i=edge[i].next) 47 { 48 v=edge[i].v; 49 if(dis[v]>dis[u]+edge[i].w) 50 { 51 dis[v]=dis[u]+edge[i].w; 52 if(!inq[v]) 53 { 54 inq[v]=1,que.push(v); 55 if(++cnt[v]>n) return 1; 56 } 57 } 58 } 59 } 60 return 0; 61 } 62 */ 63 bool vis[N]; 64 double dis[N]; 65 bool SPFA(int u) 66 { 67 vis[u]=1; 68 for(int v,i=head[u]; i; i=edge[i].next) 69 { 70 v=edge[i].v; 71 if(dis[v]>dis[u]+edge[i].w) 72 { 73 dis[v]=dis[u]+edge[i].w; 74 if(vis[v] || SPFA(v)) 75 { 76 vis[v]=1; 77 return 1; 78 } 79 } 80 } 81 vis[u]=0; 82 return 0; 83 } 84 85 double ans,l,r,mid; 86 bool check(double x) 87 { 88 memset(edge,0,sizeof(edge)); 89 memset(head,0,sizeof(head)); 90 sumedge=0; 91 for(int v,u=1; u<=n; ++u) 92 for(int i=had[u]; i; i=e[i].next) 93 { 94 v=e[i].v; 95 ins(u,v,(double)(x*e[i].w-val[v])); 96 } 97 memset(dis,127/3,sizeof(dis)); 98 memset(vis,0,sizeof(vis)); 99 for(int i=1; i<=n; ++i) 100 if(SPFA(i)) return 1; 101 return 0; 102 } 103 104 int Presist() 105 { 106 // freopen("sugar.in","r",stdin); 107 // freopen("sugra.out","w",stdout); 108 109 read(n),read(m); 110 for(int i=1; i<=n; ++i) read(val[i]),r+=val[i]; 111 for(int u,v,w,i=1; i<=m; ++i) 112 read(u),read(v),read(w),insert(u,v,w); 113 for(l=0.0,r*=1.0; l+0.00001<r; ) 114 { 115 mid=(l+r)/2.0; 116 if(check(mid)) 117 { 118 ans=mid; 119 l=mid; 120 } 121 else r=mid; 122 } 123 printf("%.2lf",ans); 124 return 0; 125 } 126 127 int Aptal=Presist(); 128 int main(){;} 洛谷評測 DFS 16ms，BFS 960，考試BFS被卡7個點，DFS快速AC?
轉載于:https://www.cnblogs.com/Shy-key/p/7526835.html
總結
- 上一篇： 包含contains
- 下一篇： CCF - 201503-3 - 节日