第一次写博客，有点小小的激动QAQ。表决心，谈理想之类的话就不多说了，反正平时说的也够多了。上大学之后才了解到算法竞赛到底是个什么东西。高一的时候一位清华的教授还来过我们学校普及了信息学奥赛，当时讲了一道例题，上了大学之后才知道，原来，，那是汉诺塔。有点遗憾，在江苏这样一个试卷难考生多招生名额少的地方，信息学竞赛普及度真的很低。有时候会想，如果我能够有条件在初中甚至小学就接触编程，现在的我会不会不一样。
上大学之后的我真的变了一个人了吧，或许是高考的失利带给我的感触与变化。不少人理解不了，上大学之后的我为什么拼命地学，因为他们不懂，在这里，我终于可以不用像以前一样，所有的努力，所有的能力只被最后的一场考试定义。一位超级优秀的学妹曾经问过我，“学长，你有明确的目标么”。当时，我哑口无言，才发现原来我只知道埋头，却不知道自己要去哪。现在，我终于明白，也终于找到了。
进入南理工的第一天起，我发誓我要在这里做到最好，到目前为止，有很多事情自己做的很不错，但也有不少事情，自己能清楚感受到差距的存在，就比如眼前的算法竞赛。的确不少比我厉害的人是因为大学以前的基础，但仍然有许许多多像我一样从零开始的人啊。所有的不成功，都应该首先从自身努力程度上找原因吧。记住，你要在这里做到最好，那就必须让你的努力配得上你所期望的成就。
-----------------------------------------------------------------------手动分割线，进入正题…………^.^
前天突然高烧，养了两天病。原来在宿舍里偷偷待一天这么爽（仅此一次，下不为例）。
错过了昨晚的div3，今天下午汇编课上机的时间就用来写了写（每天这么多人找我DEBUG挺烦的其实。）。花了一个小时左右，过了四道题，印象中还没有比这更快过，大概是因为，这次前几题简单？？粗略估计了一下罚时，如果放在昨晚的话，大概可以排到800名,错过了一次绝佳的上分机会（可惜没如果~-~）。
A题
C++
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define scan(i) scanf("%d",&i) 4 int a[10]; 5 int main(){ 6 for(int i=1;i<=4;i++){ 7 scan(a[i]); 8 } 9 sort(a+1,a+5); 10 for(int i=1;i<=3;i++){ 11 int x=a[4]-a[i]; 12 printf("%d ",x); 13 } 14 return 0; 15 }
我还是个病人，先睡觉了。明天再来哈。
Python
1 a, b, c, d = sorted(map(int, input().split())) 2 print(d-a, d-b, d-c)
只要两行，有点气人唉
B题
这道题也很简单，只要细心一点把所有情况考虑全就可以了。对于一组数，可以对每一个数进行三种操作，加一个D，减一个D，或者不变。注意，对于这一组数，正数D的值是固定的。那么首先需要考虑的是这一组数是由多少个不同的值组成，可以用一下unique函数，（！！！用之前一定要先排序！！上次因为这个问题卡了好久）。如果组成这一组数的值超过三个，那么一定不存在D满足条件。如果正好是三个，则判断是否成等差数列。
而对于一个或两个的情况，D一定存在，此时需要找一个最小的D。如果是一个，那么D显然是0。而，如果是两个的话，则要分情况，如果两数之差为偶数，则输出差的一半。而如果两数之差为奇数，则只能将其中一个变为另外一个，输出两数之差。
C++
1 #include <bits/stdc++.h> 2 using namespace std; 3 int a[105]; 4 #define scan(i) scanf("%d",&i) 5 int main(){ 6 int n;scan(n); 7 for(int i=1;i<=n;i++)scan(a[i]); 8 sort(a+1,a+n+1); 9 int x=unique(a+1,a+n+1)-(a+1); 10 if(x>=4)cout<<-1; 11 else if(x==3){ 12 if((a[2]-a[1])==(a[3]-a[2]))cout<<(a[2]-a[1]); 13 else cout<<-1; 14 } 15 else if(x==2){ 16 if((a[2]+a[1])%2==0)cout<<(a[2]+a[1])/2-a[1]; 17 else cout<<(a[2]-a[1]); 18 } 19 else cout<<0; 20 return 0; 21 }
Python
1 input() 2 a = list(set(list(map(int, input().split())))) 3 a = sorted(a) 4 if len(a) == 1:print(0) 5 elif len(a) == 2: 6 x = a[1]-a[0] 7 if x % 2 == 0: 8 x = x/2 9 print(int(x)) 10 else:print(x) 11 elif len(a)==3: 12 x = a[1] - a[0] 13 if a[2] - a[1] == x: 14 print(x) 15 else:print(-1) 16 else:print(-1)
python只要先把列表转换为集合，再把集合转换为列表，一条语句就很方便的完成了去重的过程。不过python真心慢啊，时长用了c++的四倍。
C题
没错，又是一道模拟题，我这种菜鸡也就只能写写这种模拟题了。首先算一下所有食物至多能够坚持多少个星期，然后再对从周一到周日出发七种情况进行模拟，得出最长天数就好了
1 #include <bits/stdc++.h> 2 using namespace std; 3 int a,b,c; 4 char w[8]={'.','a','b','c','a','c','b','a'}; 5 int getday(int d){ #d为1到7，分别表示周一到周日 6 int a1=a,b1=b,c1=c; #存储去除整周之后剩余的食物 7 int cnt=0; 8 while(1){ 9 if(w[d]=='a'){ 10 if(a1==0)break; 11 else{ 12 a1--;cnt++; 13 } 14 } 15 else if(w[d]=='b'){ 16 if(b1==0)break; 17 else{ 18 b1--;cnt++; 19 } 20 } 21 else{ 22 if(c1==0)break; 23 else{ 24 c1--;cnt++; 25 } 26 } 27 if(d==7)d=1; #表示已经到周日了，下一天应该是周一 28 else d++; 29 } 30 return cnt; 31 } 32 int main(){ 33 scanf("%d%d%d",&a,&b,&c); 34 int i1=a/3,i2=b/2,i3=c/2; 35 int i=min(i1,i2);i=min(i,i3); 36 long long day=7*i; 37 a-=3*i;b-=2*i;c-=2*i; 38 int ma=0; 39 for(int i=1;i<=7;i++){ 40 if(getday(i)>ma)ma=getday(i); 41 } 42 day+=ma; 43 printf("%lld",day); 44 return 0; 45 }
老师说一个厉害的程序员，main函数应该是相当整洁的。像这种对不同情况模拟取最优值的情况，尽量的用函数去写吧。
D题
这道题是一条普通的的贪心。只要想清楚一个问题就好了，在有阳光照射的地方，如果用电池，电池减一但收集器加一，也就是没有损耗，但如果用收集器，总能量就减一，为了尽量跑的远，就需要尽可能的在有阳光的地方用电池，这样一来，在没有阳光的地方，就需要尽可能的不用电池。注意，收集器有最大容量。
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn=2e5+5; 4 int m[maxn]; 5 int n,b,a; 6 int flag=1; 7 #define scan(i) scanf("%d",&i) 8 int main(){ 9 scan(n);scan(b);scan(a); 10 for(int i=1;i<=n;i++)scan(m[i]); 11 int i;int a1=a; 12 for(i=1;i<=n;i++){ 13 if(a1==0&&b==0){ 14 flag=0; 15 cout<<(i-1);break; 16 } 17 if(m[i]==1){ 18 if(b&&a1<a){ 19 b--;a1++; 20 } 21 else{ 22 a1--; 23 } 24 } 25 else{ 26 if(a1)a1--; 27 else b--; 28 } 29 if(a1==0&&b==0){ 30 flag=0; 31 cout<<i;break; 32 } 33 } 34 if(flag)cout<<n; #wa了一次，就是因为没有这条语句。忘记了走完全部路程之后的输出。 35 return 0; 36 }
看到这题，想起来上学期期末那段时间写的一道dp，也是一个路程中能量补给的问题。（话说那段时间是真轻松，整个一月几乎没课，期末考又没压力，偷偷带了电脑写代码^-^）
龟兔赛跑
Time Limit: 1000/1000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)
最近正值HDU举办50周年校庆，社会各大名流齐聚下沙，兔子也趁此机会向乌龟发起挑战。虽然乌龟深知获胜希望不大，不过迫于舆论压力，只能接受挑战。
比赛是设在一条笔直的道路上，长度为L米，规则很简单，谁先到达终点谁就算获胜。
无奈乌龟自从上次获胜以后，成了名龟，被一些八卦杂志称为“动物界的刘翔”，广告不断，手头也有了不少积蓄。为了能够再赢兔子，乌龟不惜花下血本买了最先
比赛马上开始了，兔子和带着充满电的电动车的乌龟并列站在起跑线上。你的任务就是写个程序，判断乌龟用最佳的方案进军时，能不能赢了一直以恒定速度奔跑
Input
第一行是一个整数L代表跑道的总长度
第二行包含三个整数N，C，T，分别表示充电站的个数，电动车冲满电以后能行驶的距离以及每次充电所需要的时间
第三行也是三个整数VR，VT1，VT2，分别表示兔子跑步的速度，乌龟开电动车的速度，乌龟脚蹬电动车的速度
第四行包含了N(N<=100)个整数p1,p2...pn,分别表示各个充电站离跑道起点的距离，其中0<p1<p2<...<pn<L
其中每个数都在32位整型范围之内。
Output
题目数据保证不会出现乌龟和兔子同时到达的情况。
这道题，当时想了好久。这是我第一次知道动态规划这个东西。自己写的时候，就当做贪心来处理，果不其然的wa了，还满以为自己想的没错，我在每走一步之前都选择的是到下一步时间最短的方法，
最后的总时长理应也是最短的呀。好吧，当时的想法真愚蠢。贪心算法大概，就是“鼠目寸光”吧，只想着眼前的利益，却忘了要得到的是什么，而用动态规划的话，大概就是“运筹帷幄，决胜千里”的感觉
吧，只要保证最后结果最优化。中间的某一些点之间或许没有贪心得到的效果好，但这一点小牺牲是为了换取更大的利益。运筹学真的是一门很深的学问，有机会一定要好好钻研。
状态转移方程很简单 dp[i]=min(dp[i],dp[j]+time) j<i 其余的一些附加条件计算稍微繁琐一点，小心写就好了。
1 #include <iostream> 2 using namespace std; 3 int path[102]; 4 double dp[102]; 5 int main() { 6 int L, N, C, T, vr, vt1, vt2; 7 while (cin >> L) { 8 cin >> N >> C >> T; 9 cin >> vr >> vt1 >> vt2; 10 for (int i = 1; i <= N; ++i) 11 cin >> path[i]; 12 path[0] = 0; path[N + 1] = L; 13 dp[0] = 0; 14 for(int i=1;i<=N+1;i++){ 15 double min=1000000; 16 for(int j=0;j<i;++j){ 17 double temp; 18 if(path[i]-path[j]>=C) 19 temp = dp[j] + C * 1.0 / vt1 + (path[i] - path[j] - C)*1.0 / vt2; 20 else 21 temp=dp[j]+(path[i]-path[j])*1.0/vt1; 22 if(j>0) 23 temp+=T; 24 if(temp<min) 25 min=temp; 26 } 27 dp[i] = min; 28 } 29 double rt; 30 rt = L * 1.0 / vr; 31 if(dp[N+1]<rt) 32 cout<<"What a pity rabbit!"<<endl; 33 else 34 cout<<"Good job,rabbit!"<<endl; 35 } 36 return 0; 37 }
E题
还是模拟。。。。。终于用了一回上学期学过的手写链表，虽然会有一点麻烦，皮一下依然很开心。这题主要要说的，就是如何快速，找到当前情况下存在的最大值，和最大值对应的下标。
用一个check数组保存每一个值的状态，这样在寻找最大值的时候，可以从n开始，如果这个值已经被用过了，就减一再判断，直到找到当前未用的最大值。然后用position数组保存每一个值的下标，方便索引。
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn=2e5+5; 4 int n,k,x; 5 struct node{ 6 int val; 7 int id; 8 node *pre; 9 node *next; 10 }; 11 node p[maxn]; 12 int ans[maxn]; 13 int position[maxn]; 14 bool check[maxn]; 15 inline void build(){ 16 for(int i=1;i<=n;i++){ 17 scanf("%d",&x); 18 p[i].val=x; 19 p[i].id=i; 20 p[i].pre=&p[i-1];p[i].next=&p[i+1]; 21 if(i==1)p[i].pre=NULL; 22 if(i==n)p[i].next=NULL; 23 position[x]=i; 24 } 25 return; 26 } 27 int main(){ 28 scanf("%d%d",&n,&k); 29 build(); 30 int ma=n; 31 int an=1; 32 while(ma!=0){ 33 check[ma]=true; 34 ans[position[ma]]=an; 35 int po=position[ma]; 36 int k1=k;int k2=k; 37 int p1=po,p2=po; 38 while(k1--){ 39 if(p[po].next==NULL)break; 40 int v=p[po].next->val; 41 check[v]=true; 42 ans[position[v]]=an; 43 p1=p[po].next->id; 44 p[po].next=p[po].next->next; 45 } 46 while(k2--){ 47 if(p[po].pre==NULL)break; 48 int v=p[po].pre->val; 49 check[v]=true; 50 ans[position[v]]=an; 51 p2=p[po].pre->id; 52 p[po].pre=p[po].pre->pre; 53 } 54 if(p[p1].next!=NULL)p1=p[p1].next->id; 55 else p1=n+1; 56 if(p[p2].pre!=NULL)p2=p[p2].pre->id; 57 else p2=0; 58 if(p1<=n&&p2>=1){ 59 p[p1].pre=&p[p2]; 60 p[p2].next=&p[p1]; 61 } 62 if(p1<=n&&p2<1)p[p1].pre=NULL; 63 if(p1>n&&p2>=1)p[p2].next=NULL; 64 if(an==1)an=2;else an=1; 65 while(check[ma])ma--; 66 } 67 for(int i=1;i<=n;i++) 68 printf("%d",ans[i]); 69 return 0; 70 }
未完待续。。。。。。