T1 P4771
难在读题？
发现在北边的意思就是向北走的比向东西走的多，所以对于每个兵，不断向上枚举一个倒金字塔就行了。
如果在这个金字塔中搜到山，就把答案记为金字塔层数好了。
记得预处理山
Code:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int e[1005][1005],im[1005][1005];
struct node
{
int x,y;
}a[100005];
int cnt[1005]={0};
int n,m,k;
int f=0;
int main()
{
scanf("%d%d%d",&n,&m,&k);
memset(e,0,sizeof(e));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++) scanf("%d",&e[i][j]);
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(e[i-1][j]<=e[i][j]&&e[i+1][j]<=e[i][j]&&e[i][j-1]<=e[i][j]&&e[i][j+1]<=e[i][j]) im[i][j]=1;
}
}
for(int i=1;i<=k;i++) scanf("%d%d",&a[i].x,&a[i].y);
for(int i=1;i<=k;i++)
{
/*if(a[i].x==1)
{
printf("Pool Babingbaboom!
");
continue;
}*/
f=0;
for(int j=0;j<=a[i].x;j++)
{
for(int k=a[i].y-j;k<=min(m,a[i].y+j);k++)
{
if(im[a[i].x-j][k])
{
f=1;
printf("%d
",j);
break;
}
}
if(f) break;
}
if(!f) printf("Pool Babingbaboom!
");
}
return 0;
}
坑点：不要特判(a_i.x=1), 因为他有可能就在山上。
复杂度:最坏(O(nm+nmk)),但经过(break)的玄学优化，降到了一个可以接受的值，不过还是犹豫了老长时间，考虑(n)个树状数组可还行?。
(正解是(dp)???)
T2 P3619
显然是个贪心题
窝是这么考虑的：
对于(d_i>0)的部分，总体是积累的，所以要求越高越要放后面（积累积累说不定就满足了呢）；
对于(d_i<0)的部分，总体是消耗的，所以要求越低越低的越要后做；
总体上先做(d_i>0)的部分。
可以用两个堆维护，对吧？
Code:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
priority_queue<pair<int,int> >q1,q2;
int z,n,t;
int tt[100005],b[100005];
int f=0;
int main()
{
scanf("%d",&z);
while(z--)
{
f=0;
scanf("%d%d",&n,&t);
//while(!q.empty()) q.pop();
for(int i=1;i<=n;i++)
{
scanf("%d%d",&tt[i],&b[i]);
if(b[i]>=0) q1.push(make_pair(-tt[i],b[i]));
else q2.push(make_pair(tt[i],b[i]));
}
while(!q1.empty())
{
int x=-q1.top().first,y=q1.top().second;
if(t<x) f=1;
else t+=y;
q1.pop();
}
while(!q2.empty())
{
int x=q2.top().first,y=q2.top().second;//多打了个负号竟然不影响分数？？
if(t<x) f=1;
else t+=y;
if(t<=0) f=1;
q2.pop();
}
if(f) printf("-1s
");
else printf("+1s
");
}
return 0;
}
然而只有91分，AFO了！！！
经过很长时间的努力，终于在考试结束后找到一组(hack)数据（还有用吗）：
1
2 7
3 -1
5 -5
显然我还是太弱了，正解是将(b_i<0)的部分按(t_i+b_i)从大到小发的排序（虽然我不会证）。
T3 P3245
照例不会，不过至少读懂题了，我们显然可以对(n^2)个子串跑高精除低精，复杂度是(O(n^2))的，不过常数很大，使得我收获了11分的好成绩。
值得一提的是，我自己(yy)出了压位高精，不过(ans[])玄学赋值真的坑害了我呢！！
不嫌的话，发下(code):
Code:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
bool div(char a[],int l,int r,int b)
{
int cnt=1,ans[10005],la=r-l+1;
memset(ans,0,sizeof(ans));//死了
int j=1;
for(int i=r;i>=l;i--)
{
int k=a[i]-'0';
ans[cnt]+=k*pow(10,j-1);
j++;
if(j==6) j=1,cnt++;
}
for(int i=cnt;i>=2;i--) ans[i-1]+=(ans[i]%b)*100000;
ans[1]%=b;
if(ans[1]==0) return true;
else return false;
}
char s[10005];
int n,p,f,t,ans;
int si[10005][10005];
int main()
{
int m;
scanf("%d",&p);
scanf("%s",s);
scanf("%d",&n);
int l=strlen(s);
for(int i=1;i<=l;i++)
{
for(int j=i;j<=l;j++)
{
if(div(s,i-1,j-1,p)) si[i][j]=1;
}
}
for(int i=1;i<=n;i++)
{
ans=0;
scanf("%d%d",&f,&t);
for(int k=f;k<=t;k++)
{
for(int j=k;j<=t;j++)
{
if(si[k][j]) ans++;
}
}
printf("%d
",ans);
}
return 0;
}
好了，这次模拟考试收获了100+91+11=202的好成绩，没遇到什么算法题，思维难度道挺高，还是技不如人哪。
这都改变不了我弱的本质。