题目：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3633
题意：给你一个n个数字组成的串，同时有m个询问，问第a个数字和第b个数字之间是否存在相同的数，没有就输出"OK",存在就输出最右边出现的重复的数。
题解：线段树可以过，维护一个标志数组，flag[x]代表第x个段是否有重复的数，有重复的就是储存重复的数值，没有就存-1.对于一个区间，如果它的右子区间有重复的数，那它就等于它的右子区间，右子区间没有重复的数就是把左右区间合并起来找有没有重复的数，如果还没有那这个区间就等于它左子区间的值。
代码：
#include<cstdio>
#include<cstring>
#include<set>
using namespace std;
#define MAX 500005
int value[MAX];
int flag[MAX<<2];//-1代表没有重复的，正数代表右边开始第一个重复的
set<int> hashx;
void push_up(int l,int r,int idx)
{
if(flag[idx<<1|1]!=-1)
{
flag[idx]=flag[idx<<1|1];
return;
}
hashx.clear();
int mid=(l+r)>>1;
//从左子区间的最右边开始，在右子区间里查找有没有相同的
for(int i=mid+1;i<=r;++i) hashx.insert(value[i]);
for(int i=mid;i>=l;--i)
{
if(hashx.count(value[i])==0)
hashx.insert(value[i]);
else
{
flag[idx]=value[i];
return;
}
}
flag[idx]=flag[idx<<1];
return;
}
void build(int l,int r,int idx)
{
if(l==r)
{
flag[idx]=-1;
return;
}
int mid=(l+r)>>1;
build(l,mid,idx<<1);
build(mid+1,r,idx<<1|1);
push_up(l,r,idx);
}
int query(int a,int b,int l,int r,int idx)
{
if(a<=l&&r<=b) return flag[idx];
int mid=(l+r)>>1;
int x,y;
x=y=-1;
if(b<=mid) return query(a,b,l,mid,idx<<1);
if(mid<a) return query(a,b,mid+1,r,idx<<1|1);
if(mid<b) y=query(a,b,mid+1,r,idx<<1|1);
if(y!=-1) return y;
hashx.clear();
for(int i=mid+1;i<=b;++i) hashx.insert(value[i]);
for(int i=mid;i>=a;--i)
{
if(hashx.count(value[i])==0)
hashx.insert(value[i]);
else
return value[i];
}
return query(a,mid,l,mid,idx<<1);
}
int main()
{
int n,m,k;
int a,b;
for(;~scanf("%d",&n);)
{
for(int i=1;i<=n;++i)
scanf("%d",value+i);
build(1,n,1);
scanf("%d",&m);
for(;m--;)
{
scanf("%d%d",&a,&b);
int ans=query(a,b,1,n,1);
if(ans==-1) puts("OK");
else printf("%d\n",ans);
}
puts("");
}
return 0;
}
Cinema in Akiba
题意：告诉你第i个人买票的时候要买从左往右数空位中第j个空位，问你n个人分别买了哪个位置的票。
题解：线段树。维护区间内空座位数。
代码：
#include<cstdio>
#include<cstring>
using namespace std;
#define MAX 50005
int summ[MAX<<2];
int indx[MAX];
void push_up(int idx)
{
summ[idx]=summ[idx<<1]+summ[idx<<1|1];
}
void build(int l,int r,int idx)
{
summ[idx]=1;
if(l==r) return;
int mid=(l+r)>>1;
build(l,mid,idx<<1);
build(mid+1,r,idx<<1|1);
push_up(idx);
}
int update(int x,int l,int r,int idx)
{
if(l==r)
{
summ[idx]=0;
return l;
}
int mid=(l+r)>>1;
int ans;
if(x<=summ[idx<<1]) ans=update(x,l,mid,idx<<1);
else ans=update(x-summ[idx<<1],mid+1,r,idx<<1|1);
push_up(idx);
return ans;
}
int main()
{
int n,m,k;
for(;~scanf("%d",&n);)
{
build(1,n,1);
for(int i=1;i<=n;++i)
{
scanf("%d",&k);
indx[i]=update(k,1,n,1);
}
scanf("%d",&m);
for(int i=1;i<=m;++i)
{
scanf("%d",&k);
if(i==1) printf("%d",indx[k]);
else printf(" %d",indx[k]);
}
puts("");
}
return 0;
}
题意：给你一些可选课程，同时给出课程的上课范围和该课程的学分，让你排一个能获得最大学分的课程表（课程时间不能冲突），问最大学分是多少。
题解：课程的时间范围给的有点变态啊，竟然是月日时分的，我是把这个换算成分钟为单位的值。这样题目就转换成给你一些一维线段和线段的权值，让你选出一些不重叠的线段，使得权值最大。这个果断的DP啊，就是状态不太好表示。我的方法首先按线段的右端点从小到大排序，dp[i]表示前i个线段的最大权值和，转移为dp[i]=max(max[i-1],dp[p[i]]+value[i])，p[i]为前i中与i不相交的线段的最大下标，这可以通过二分查找提前处理好。
代码：
#include<cstdio>
#include<string>
#include<map>
#include<cstring>
#include<algorithm>
#include<ctype.h>
#define max(a,b) ((a)>(b)?(a):(b))
#define MAX 100005
using namespace std;
struct cla
{
int st,en;
double cred;
} stud[MAX];
int p[MAX];
double dp[MAX];
int n;
bool cmp(const struct cla &a,const struct cla &b)
{
return a.en==b.en?(a.st<b.st):(a.en<b.en);
}
int binarySearch(int x)
{
int l=0,r=n-1,mid;
if(x<stud[0].en) return -1;
for(;l<r;)
{
mid=(l+r+1)>>1;
if(stud[mid].en<=x)
l=mid;
else
r=mid-1;
}
return l;
}
map<string,int> hashx;
int monthtime[15]= {0,31,60,91,121,152,182,213,244,274,305,335,366};
int charToInt(char *c)
{
int num=0;
for(int i=0; i<strlen(c)&&c[i]>='0'&&c[i]<='9'; ++i)
num=(num*10)+c[i]-'0';
return num;
}
int main()
{
int a,b;
int cnt,dayint;
char month[25],day[25],time[25];
hashx.insert(make_pair("jan",0));
hashx.insert(make_pair("feb",1));
hashx.insert(make_pair("mar",2));
hashx.insert(make_pair("apr",3));
hashx.insert(make_pair("may",4));
hashx.insert(make_pair("jun",5));
hashx.insert(make_pair("jul",6));
hashx.insert(make_pair("aug",7));
hashx.insert(make_pair("sep",8));
hashx.insert(make_pair("oct",9));
hashx.insert(make_pair("nov",10));
hashx.insert(make_pair("dec",11));
for(; ~scanf("%d",&n);)
{
for(int i=0; i<n; ++i)
{
cnt=0;
scanf("%s%s",month,day);
scanf("%d:%d",&a,&b);
scanf("%s",time);
for(int j=0; j<strlen(month); ++j)
month[j]=tolower(month[j]);
dayint=charToInt(day);
cnt+=((monthtime[hashx.find(string(month))->second]+dayint)*24*60+a*60+b);
if(strcmp(time,"p.m.")==0) cnt+=(12*60);
stud[i].st=cnt;
cnt=0;
scanf("%s%s",month,day);
scanf("%d:%d",&a,&b);
scanf("%s",time);
for(int j=0; j<strlen(month); ++j)
month[j]=tolower(month[j]);
dayint=charToInt(day);
cnt+=((monthtime[hashx.find(string(month))->second]+dayint)*24*60+a*60+b);
if(strcmp(time,"p.m.")==0) cnt+=(12*60);
stud[i].en=cnt+5;
scanf("%lf",&stud[i].cred);
}
sort(stud,stud+n,cmp);
int front=0;
for(int i=0; i<=n; ++i)
dp[i]=0;
for(int i=0; i<n; ++i)
p[i]=binarySearch(stud[i].st);
dp[0]=stud[0].cred;
double maxx=dp[0];
for(int i=1; i<n; ++i)
{
if(p[i]==-1) dp[i]=max(dp[i-1],stud[i].cred);
else dp[i]=max(dp[i-1],dp[p[i]]+stud[i].cred);
if(maxx<dp[i])
maxx=dp[i];
}
printf("%.1f\n",maxx);
}
return 0;
}
题意：看题目的提示就懂了。
题解：栈模拟。
代码：
#include<cstdio>
#include<cstring>
char m[512010],z[300],flag[512010];
int main()
{
int ans,top;
for(;~scanf("%s%s",z,m);)
{
ans=0,top=1;
int len=strlen(z);
for(int i=0;m[i];++i)
{
flag[top-1]=m[i];
if(top>=len)
{
flag[top]=0;
if(strcmp(flag+top-len,z)==0)
{
top-=len;
ans++;
}
}
top++;
}
printf("%d\n",ans);
}
return 0;
}