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(){;}
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 ",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(){;}
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(){;}