【A HDU1372 】点击打开链接
【解题方法】不能再裸的爆搜了，没什么解释的。
【AC代码】
///@zxy
///2015/8/2
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<iostream>
using namespace std;
char s[20],e[20];
int sx,sy,ex,ey;
int vis[9][9];
int dir[8][2]={{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1},{-2,1},{-1,2}};
struct node{
int x,y,step;
};
int bfs(int sx,int sy)
{
node cur,pp;
int dx,dy;
queue<node>qq;
vis[sx][sy]=true;
cur.x=sx,cur.y=sy,cur.step=0;
if(cur.x==ex&&cur.y==ey)
return cur.step;
qq.push(cur);
while(!qq.empty())
{
cur=qq.front();
qq.pop();
if(cur.x==ex&&cur.y==ey)
return cur.step;
for(int i=0;i<8;i++)
{
dx=cur.x+dir[i][0];
dy=cur.y+dir[i][1];
while(dx>=1&&dx<=8&&dy>=1&&dy<=8&&!vis[dx][dy])
{
pp.x=dx;
pp.y=dy;
pp.step=cur.step+1;
qq.push(pp);
vis[dx][dy]=true;
}
}
}
}
int main()
{
while(scanf("%s%s",s,e)!=EOF)
{
sx=s[1]-'0';
sy=s[0]-'a'+1;
ex=e[1]-'0';
ey=e[0]-'a'+1;
memset(vis,false,sizeof(vis));
printf("To get from %s to %s takes %d knight moves.\n",s,e,bfs(sx,sy));
}
return 0;
}【解题方法】签到题，计算一个等比数列的和，然后加一加，减一减就搞定了。
【AC 代码】
typedef long long LL;
LL a[64];
int main()
{
a[0]=1;
for(int i=1;i<=64;i++)
a[i]=a[i-1]*2;
int tt;
LL n;
scanf("%d",&tt);
while(tt--)
{
scanf("%I64d",&n);
LL ans=(n+1)*n/2;
for(int i=0;a[i]<=n;i++)
ans-=2*a[i];
printf("%I64d\n",ans);
}
return 0;
}【C POJ3667】
【解题方法】简单的区间合并，线段树维护一个区间从左端点，右端点开始的空房间，然后再维护一个总的空房间。然后区间合并即可！
【AC 代码】
<pre name="code" class="cpp">//Created Author :just_sort
//Created Time :2016/3/2 18:49
//Created File :Hotel.
/**************************/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define maxn 50010
int getInt(int &x)
{
return scanf("%d",&x);
}
void read(int &tmp)
{
tmp=0;
char ch=getchar();
int fu=1;
for(; ch<'0'||ch>'9'; ch=getchar())
if(ch=='-')fu=-1;
for(; ch>='0'&&ch<='9'; ch=getchar())
tmp=tmp*10+ch-'0';
tmp*=fu;
}
int lsum[maxn<<2],rsum[maxn<<2],msum[maxn<<2];//
int cover[maxn<<2];//打标记
void Push_Down(int rt,int m)
{
if(cover[rt]!=-1)
{
cover[rt<<1]=cover[rt<<1|1]=cover[rt];
msum[rt<<1]=lsum[rt<<1]=rsum[rt<<1]=cover[rt]?0:m-(m>>1);
msum[rt<<1|1]=lsum[rt<<1|1]=rsum[rt<<1|1]=cover[rt]?0:(m>>1);
cover[rt]=-1;
}
}
void Push_Up(int rt,int m)
{
lsum[rt]=lsum[rt<<1];
rsum[rt]=rsum[rt<<1|1];
if(lsum[rt]==m-(m>>1)) lsum[rt]+=lsum[rt<<1|1];
if(rsum[rt]==(m>>1)) rsum[rt]+=rsum[rt<<1];
msum[rt]=max(max(msum[rt<<1],msum[rt<<1|1]),lsum[rt<<1|1]+rsum[rt<<1]);
}
void Build(int l,int r,int rt)
{
cover[rt]=-1;
lsum[rt]=rsum[rt]=msum[rt]=r-l+1;
if(l==r) return ;
int m=(l+r)>>1;
Build(lson);
Build(rson);
}
void Update(int L,int R,int c,int l,int r,int rt)
{
if(L<=l&&r<=R)
{
msum[rt]=lsum[rt]=rsum[rt]=c?0:r-l+1;
cover[rt]=c;
return ;
}
Push_Down(rt,r-l+1);
int m=(l+r)>>1;
if(L<=m) Update(L,R,c,lson);
if(m<R) Update(L,R,c,rson);
Push_Up(rt,r-l+1);
}
int query_ans(int len,int l,int r,int rt)//查询是长度为len的空房间的位置
{
if(l==r)return l;
Push_Down(rt,r-l+1);
int m=(l+r)>>1;
if(msum[rt<<1]>=len) return query_ans(len,lson);
else if(rsum[rt<<1]+lsum[rt<<1|1]>=len) return m-rsum[rt<<1]+1;
else return query_ans(len,rson);
}
int main()
{
int n,m,a,b,type;
read(n);
read(m);
Build(1,n,1);
while(m--)
{
read(type);
if(type==1)
{
read(a);
if(a>msum[1])puts("0");
else
{
int ans=query_ans(a,1,n,1);
printf("%d\n",ans);
Update(ans,ans+a-1,1,1,n,1);
}
}
else
{
read(a);
read(b);
Update(a,a+b-1,0,1,n,1);
}
}
return 0;
}
【D HDU5499】
【解题方法】签到题2，结构体排序即可。
【AC代码】
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn = 100005;
struct ss
{
int mal,r1,r2;
double score;
char name[50];
}st[108];
char s[50];
int maxr1,maxr2;
bool cmp(ss a,ss b)
{
return a.score>b.score;
}
int main()
{
int t;
int n,m;
scanf("%d",&t);
while(t--)
{
int vis=0;
maxr1=maxr2=0;
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
{
scanf("%s%s%d%d",st[i].name,s,&st[i].r1,&st[i].r2);
if(s[0]=='m') st[i].mal=1;
else
{
st[i].mal=0;
vis=1;
}
maxr1=max(st[i].r1,maxr1);
maxr2=max(st[i].r2,maxr2);
}
printf("The member list of Shandong team is as follows:\n");
for(int i=0;i<n;i++)
{
st[i].score=(double) st[i].r1*(90.00/(maxr1*1.00) ) +(double) st[i].r2*(210.00/ (maxr2*1.00));
}
sort(st,st+n,cmp);
for(int i=0;i<m-1;i++)
{
printf("%s\n",st[i].name);
if(st[i].mal==0)
{
vis=0;
}
}
if(vis)
{
for(int i=m-1;i<n;i++)
{
if(!st[i].mal)
{
printf("%s\n",st[i].name);
break;
}
}
}
else printf("%s\n",st[m-1].name);
}
}【E Codeforences 469 C】
【解题方法】这题主要考得是你聪不聪明，完全spj想法题，想到了就非常简单。
【AC 代码】
#include <bits/stdc++.h>
using namespace std;
int n;
int main()
{
cin>>n;
if(n<=3){
puts("NO");
}else{
if(n==4){
puts("YES");
puts("2 * 4 = 8");
puts("3 * 8 = 24");
puts("1 * 24 = 24");
}else if(n==5){
puts("YES");
puts("5 - 2 = 3");
puts("3 + 3 = 6");
puts("6 * 4 = 24");
puts("1 * 24 = 24");
}
else if(n>=6){
puts("YES");
puts("6 - 5 = 1");
puts("1 - 1 = 0");
for(int i=7; i<=n; i++){
printf("0 * %d = 0\n",i);
}
puts("2 * 3 = 6");
puts("6 * 4 = 24");
puts("0 + 24 = 24");
}
}
}【F Codeforences21C】
【解题方法】先找到2*sum,然后找sum，维护答案的时候不要忘记减掉运到的2*sum的个数，这里的sum=总和/3，因为分成3份嘛。
【AC 代码】
#include<bits/stdc++.h>
#define LL __int64
using namespace std;
LL sum[100005];
int main()
{
int n;
scanf("%d",&n);
//LL sum=0;
for(int i=1;i<=n;i++)
{
LL x;
scanf("%I64d",&x);
sum[i]=sum[i-1]+x;
}
LL ans=0;
if(sum[n]%3==0)
{
LL summ=sum[n]/3;
LL temp=0;
for(int i=1;i<=n-1;i++)
{
if(sum[i]==2*summ)
{
temp++;//有多少个前缀和=2*summ
}
}
for(int i=1;i<=n-1;i++)
{
if(sum[i]==2*summ)//如果当前位置前缀和为2*summ,那么这个位置之后的前缀和等于summ的数目-1，
temp--;
if(sum[i]==summ)//因为这个位置为summ,后面有temp个前缀和等于2*summ，i到这temp个位置之间的元素和就为2*summ-summ,这些位置之后的数和就为summ
{
ans+=temp;//所以能够分成三份
}
}
}
printf("%I64d\n",ans);
return 0;
}【G HDU4991】
【解题方法】应该算是本场最难的一个题了，dp[i][j]表示在i位置，长度为j的方案数，那么dp[i][j]=sum(dp[k][j-1]),a[k]<a[j]&&k<j，如果暴力维护肯定会T的，那么我们容易想到用BIT来维护dp[i][j]的前缀和，但是这里数很大所以我们查找位置k是需要离散化的，想到了这点，这题就完成啦！
【AC代码】
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=123456789;
const int maxn=10010;
ll a[maxn],b[maxn],c[maxn];//c用来维护dp[i][j]的前缀和
ll dp[maxn][110];//dp[i][j]表示当前位置为i,长度为j的方案数
int n,m;
int lowbit(int x){return x&(-x);}
void add(int i,int v)
{
while(i<=n){
c[i]+=v;
i+=lowbit(i);
}
}
ll getsum(int i)
{
ll ans=0;
while(i){
ans=(ans+c[i])%mod;
i-=lowbit(i);
}
return ans;
}
void init()
{
memset(c,0,sizeof(c));
memset(dp,0,sizeof(dp));
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
init();
for(int i=1; i<=n; i++) scanf("%I64d",&a[i]);
for(int i=1; i<=n; i++) b[i]=a[i];
//INIT
sort(b+1,b+n+1);
for(int i=1; i<=n; i++) dp[i][1]=1;
for(int j=2; j<=m; j++){
memset(c,0,sizeof(c));
for(int i=1; i<=n; i++){
int id=lower_bound(b+1,b+n+1,a[i])-b;
dp[i][j]=getsum(id-1);
add(id,dp[i][j-1]);
}
}
ll ans=0;
for(int i=1; i<=n; i++){
ans=(ans+dp[i][m])%mod;
}
printf("%I64d\n",ans);
}
}
京公网安备 11010502036488号