RQNOJ 考分鄙视

http://www.rqnoj.cn/Problem_509.html
这道题目挺水的,如果考试i鄙视考试j,那么Ai-Aj>i-j…就是Ai-i>Aj-j..所以把A’i=Ai-i。。就是A’i的逆序对数量了。。。。直接用树状数组。。
Code:
#include<cstdio>#include<iostream>#define rep(i,n) for(int i=0;i<n;i++)using namespace std;const int maxn=100000,maxv=20000,maxs=maxn+maxv+10,mod=12345;int C[maxs]={},n;void add(int p,int d){ for(;p<maxs;p+=(p&-p)) C[p]+=d;}int sum(int p){ int ret=0; for(;p;p-=(p&-p))ret+=C[p]; return ret;}void Plus(int&a,int b){ a+=b;if(a>=mod)a-=mod;}int main(){ //freopen("in","r",stdin); scanf("%d",&n);int x,ans=0; rep(i,n) { scanf("%d",&x);x+=maxn-i; Plus(ans,sum(x-1)); add(x,1); } printf("%dn",ans);}

RQNOJ 多人背包

www.rqnoj.cn/Problem_123.html
这道题目实际上意思就是求前K优解,效仿一般的动态规划,可以很方便的搞定这个。。只是转移的时候更新的是一个队列。。
Code:

#include<cstdio>#include<algorithm>#include<iostream>#define rep(i,n) for(int i=0;i<n;i++)const int maxk=50+1,maxv=5000+1,maxn=200,inf=~0U>>1;using namespace std;int k,v,n;struct Thing{ int w,v;}T[maxn];int tmp[maxk];struct State{ int n,A[maxk]; State(){n=0;} void put(int x){A[n++]=x;} void Update(State&s,int v) { int m=min(k,s.n+n),i=0,j=0; #define get(i) (s.A[i]+v) A[n]=-inf;s.A[s.n]=-inf; rep(o,m) { if(A[i]>get(j)) tmp[o]=A[i],i++; else tmp[o]=get(j),j++; } memcpy(A,tmp,sizeof(int)*m); n=m; }}Dp[maxv];void Init(){ scanf("%d%d%d",&k,&v,&n); rep(i,n)scanf("%d%d",&T[i].w,&T[i].v);}void Solve(){ Dp[0].put(0); rep(i,n) { for(int j=v;j>=T[i].w;j–) Dp[j].Update(Dp[j-T[i].w],T[i].v); } int ans=0; rep(i,Dp[v].n)ans+=Dp[v].A[i]; cout<<ans<<endl;}int main(){ //freopen("in","r",stdin); Init(); Solve();}

RQNOJ 找第k小的数

哎。。最近状态很颓废啊。。。
这道题题目算法地球人都知道,就是线段树+二分判定,但我WA了N次囧。。。
设当前的区间是l,r。。那么设C(x)为用线段树的在l,r中小于x的个数,那么如果当前要第k小的数,
则C(x)=k-1,同时x属于l和r之间,所以C(x+1)=k。。就是找出最大的C(x)为k-1的数。。。
Code:

#include<cstdio>#include<algorithm>#include<iostream>#define rep(i,n) for(int i=0;i<n;i++)using namespace std;const int maxn=10000+10;#define Left t*2,l,l+r>>1#define Right t*2+1,l+r>>1,rint*T[maxn*4],n,m,A[maxn],d;void Build(int t,int l,int r){ int s=r-l; T[t]=new int[s]; memcpy(T[t],A+l,sizeof(int)*s); sort(T[t],T[t]+s); if(s>1)Build(Left),Build(Right);}int get(int*D,int s,int x){ int i,l; for(i=-1,l=d;l;l>>=1) if(i+l<s&&D[i+l]<x) i+=l; return i+1;}int Count(int t,int l,int r,int a,int b,int x){ if(l>=b||r<=a)return 0; if(l>=a&&r<=b)return get(T[t],r-l,x); return Count(Left,a,b,x)+Count(Right,a,b,x);}#define Cal(x) (Count(1,0,n,a,b,x))int Ask(int a,int b,int k){ int i,l; for(i=n,l=d;l;l>>=1) if(i-l>=0&&Cal(A[i-l])>=k) i-=l; return A[i-1];}int main(){ //freopen("in","r",stdin); scanf("%d%d",&n,&m); rep(i,n)scanf("%d",A+i); Build(1,0,n);sort(A,A+n);A[n]=1e6;int l,r,k; d=1;while(d<=n)d<<=1;d>>=1; while(m–) { scanf("%d%d%d",&l,&r,&k);l–; printf("%dn",Ask(l,r,k)); }}

[AHOI1997]彩旗飘飘

www.rqnoj.cn/Problem_371.html
这道题其实很简单,但我WA了2次。。原因是搞不清楚边界条件。。
实际上往后推的方便多了囧。。一下就AC。。。
Code:
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
const int inf=~0U>>1,maxn=15+10;
using namespace std;
typedef long long ll;
ll Dp[maxn][maxn][maxn][2]={};
int main()
{
//freopen("in","r",stdin);
int n,m;cin>>n>>m;
Dp[1][0][0][0]=Dp[0][1][0][1]=1;
for(int l=1;l<n*2;l++)
for(int a=0;a<=min(l,n);a++)
{
int b=l-a;
for(int c=0;c<=m;c++)
for(int l=0;l<2;l++)
if(ll x=Dp[a][b][l])
{
Dp[a+1][b][0]+=x;
Dp[a][b+1][1]+=x;
}
}
cout<<Dp[n][n][m][0]*2<<endl;
}

[AHOI2007]密码箱

www.rqnoj.cn/Problem_296.html
我这个算法的复杂度应该是LogN*Sqrt(N)..居然AC了囧。。。
这题就是求x*x%n==1的解的个数,
也就是n|(x+1)(x-1)..设n=a*b,a<b,枚举a,那么可以考虑a|x+1&&b|x-1的情况,还有一个是对称的,这种情况下,按b的倍数枚举x,由于b>Sqrt(N)。。故最多Sqrt(N)个x,然后用个set去重就OK了。。
Code:
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <set>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
const int inf=~0U>>1;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int main()
{
//freopen("in","r",stdin);
ll n;cin>>n;set<int> S;
for(int a=1;a*a<=n;a++)
if(n%a==0)
{
int b=n/a;
for(int x=1;x<n;x+=b)
if((x+1)%a==0)
S.insert(x);
for(int x=b-1;x<n;x+=b)
if((x-1)%a==0)
S.insert(x);
}
for(set<int>::iterator i=S.begin();i!=S.end();i++)
cout<<*i<<endl;
}

[AHOI2007]宝库迷宫

www.rqnoj.cn/Problem_301.html
晕。。竟然抄TopCoder的原题。。
看上去很难,因为10^10的搜索是要悲剧的。。但实际上只要每个点中间点向左向右搜出10^5的路径然后都排序就可以直接扫描得出结果了。。
Code:
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
const int inf=~0U>>2,maxn=10,maxp=100000+10;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
struct Array
{
double A[maxp];int n;
void set(){n=0;}
Array(){set();}
void add(double x){A[n++]=x;}
void Sort(){sort(A,A+n);}
double operator[](int v){return A[v];}
};
int n;double D[maxn][maxn];
Array L,R;
void DfsL(int pos,int d,double now)
{
if(!d){L.add(now);return;}
rep(i,n)DfsL(i,d-1,now+D[i][pos]);
}
void DfsR(int pos,int d,double now)
{
if(!d){R.add(now);return;}
rep(i,n)DfsR(i,d-1,now+D[pos][i]);
}
int main()
{
//freopen("in","r",stdin);
cin>>n;rep(i,n)rep(j,n){cin>>D[i][j];}
double ans=inf;
rep(i,n)
{
int l=n/2,r=n-l;
L.set();R.set();
DfsL(i,l,0);DfsR(i,r,0);
L.Sort();R.add(inf);R.add(-inf);R.Sort();int j=R.n-1;
for(int i=0;i<L.n;i++)
{
while(L[i]+R[j]>=2007)j–;
ans=min(ans,2007-L[i]-R[j]);
ans=min(ans,L[i]+R[j+1]-2007);
}
}
printf("%0.2lfn",ans);
}

[AHOI2007]红十字

www.rqnoj.cn/Problem_300.html

题目:[AHOI2007]红十字

问题编号:300

题目描述

通往藏宝库的通道打开了,走下一段长长的楼梯,钻过一条矮矮的地道,你和小可可终于来到了藏宝库的门前。随之而来的就是最后一 个挑战,只要能打开宝库的门,里面的宝藏就是你们的了。
宝库的门依然是通过机关打开,这个门很奇怪,是一个正方形,被划分成许多大小一致的正方形 的小方格,这些方格不是红色就是白色,猛看上去这些方格组成了许多红十字状的标志。根据藏宝图记载,只要找到门上最大的红十字,按下它中心的方格,宝库的 门就能打开了。
红十字标志也是一个正方形,边长为(2k+1)*(2k+1),其中k为非负整数。它的四条边与门的边平行,而且恰由门上的 (2k+1)*(2k+1)个小方格组成。这里,红十字标志是以白色为底色,红色为十字的颜色。假设用1表示红色,用0表示白色。对应到计算机处理的数据 中,就是除了正中列与正中行全为1外,其余方格均为0。以下是几种不同大小的标志:
1*1:
1
3*3
010
111
010
5*5
00100
00100
11111
00100
00100

小 可可被这个机关难到了,现在只有靠你了,请你帮助他在这个门上找到一个最大的红十字标志,输出它的边长即可。

输入格式

输入文件中第一行有一个整数n(1<=n<=2,000),表示门由n个方格组成。
以下n行,每行n个字 符,每个字符都是0或1。数据中不会出现全为0的情况。

输出格式

输出一个数,即最大的红十字标志的边长。

样例输入 5 00011 01011 11100 01001 00010 样例输出 3 三维状态图像
这道题挺有意思啊,首先求出每个点从4个方向最多按1能延伸多少,还有从四个方向开上的最大全为0正方形。。时限太紧了。。代码写的我要吐了。。我不得已只好用了指针。。ugly Code….
Code:
www.ideone.com/gXeXg

SPOJ New Distinct Substrings

https://www.spoj.pl/problems/SUBST1/
这是经典的题目了。。求出后缀数组和Height数组,然后用n*(n+1)/2-所有Height的和就OK了囧。。。
Code:
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
const int inf=~0U>>1,maxn=50000+10;
using namespace std;
char C[maxn];int ta[maxn],tb[maxn],sa[maxn],n,m,*x=ta,*y=tb,h[maxn];
void Sort()
{
static int w[maxn];
rep(i,m)w[i]=0;rep(i,n)w[x[y[i]]]++;rep(i,m-1)w[i+1]+=w[i];
for(int i=n-1;i>=0;i–)sa[–w[x[y[i]]]]=y[i];
}
bool cmp(int a,int b,int l)
{return y[a]==y[b]&&y[a+l]==y[b+l];}
void Da()
{
rep(i,n)x[i]=C[i],y[i]=i;Sort();int i,j,p;
for(j=1,p=1;p<n;j*=2,m=p)
{
for(p=0,i=n-j;i<n;i++)y[p++]=i;
rep(i,n)if(sa[i]>=j)y[p++]=sa[i]-j;Sort();
for(swap(x,y),p=1,x[sa[0]]=0,i=1;i<n;i++)
x[sa[i]]=cmp(sa[i-1],sa[i],j)?p-1:p++;
}
}
void CalH()
{
static int R[maxn];
int i,j,k=0;
for(i=1;i<=n;i++)R[sa[i]]=i;
for(i=0;i<n;h[R[i++]]=k)
for(k?k–:0,j=sa[R[i]-1];C[i+k]==C[j+k];k++);
}
void Solve()
{
scanf("%s",C);n=strlen(C);C[n++]=0;m=256;
Da();n–;long long ans=n;ans*=n+1;ans/=2;
CalH();rep(i,n)ans-=h[i+1];cout<<ans<<endl;
}
int main()
{
//freopen("in","r",stdin);
int t;cin>>t;while(t–)Solve();
}

Suffix Array…

好不容易写了个SA的代码,以前写过但是忘掉了囧。。。
Code:
#include<cstdio>#include<algorithm>#include<iostream>#define rep(i,n) for(int i=0;i<n;i++)using namespace std;const int maxn=10000+10;char C[maxn];int n,sa[maxn],ta[maxn],tb[maxn],m,tv[maxn];void sort(int*x,int*y,int m){ static int w[maxn]; rep(i,m)w[i]=0;rep(i,n)w[x[y[i]]]++; rep(i,m)if(i)w[i]+=w[i-1]; for(int i=n-1;i>=0;i–)sa[–w[x[y[i]]]]=y[i];}inline bool cmp(int*r,int i,int j,int l){ return r[i]==r[j]&&r[i+l]==r[j+l];}void Da(){ int*x=ta,*y=tb,i,j,p; rep(i,n)x[i]=C[i],tv[i]=i;sort(x,tv,m); for(j=1,p=1;p<n;j*=2,m=p) { for(p=0,i=n-j;i<n;i++)y[p++]=i; rep(i,n)if(sa[i]>=j)y[p++]=sa[i]-j;sort(x,y,m); for(swap(x,y),p=1,x[sa[0]]=0,i=1;i<n;i++) x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++; }}int main(){ scanf("%s",C);n=strlen(C);C[n++]=0;m=’Z’+1; Da(); rep(i,n)printf("%dn",sa[i]);}

Page 3 of 41234