/**//*
如果N是偶數，那么X^N =（X*X）^[N/2]；
如果N是奇數，那么X^N = X*X^(N-1) = X *（X*X）^[N/2]；
*/
int powermod(int a, int b, int p)//a^b % p
{
if(b==0) return 1;
int t=powermod((a*a)%p, b/2, p);
if(b&1!=0) t=(t*a)%p;
return t;
}int modexp(int a,int b, int p)
{
int t=1,;
while(b!=0)
{
if(b%2) t=(t*a)%p;
a=(a*a)%p;
b/=2;
}
return t;
}
posted @
2010-03-28 22:57 wyiu 閱讀(147) |
評論 (0) |
編輯 收藏
//離散化+st ?
#include <iostream>
#include <math.h>
using namespace std;
int a[100005];
int index[100005];
int f[100005];
int start[100005];
int mf[100005][100];
int n;
void rmq_init()
{
int i,j,k=floor(log(double(n))/log(2.0));
for(i=1; i<=n; i++) mf[i][0]=f[i];
for(j=1; j<=k; j++)
for(i=1; i+(1<<(j-1))<=n; i++)
mf[i][j]=max(mf[i][j-1],mf[i+(1<<(j-1))][j-1]);
}
int rmq(int l,int r)
{
int il,ir, m,k;
il=index[a[l]],ir=index[a[r]];
if(il==ir)
return r-l+1;
else
if(il+1==ir)
return max(start[ir]-l, r-start[ir]+1);
else
{
m=max( start[il+1]-l, r-start[ir]+1);
il++,ir--;
k=floor(log(double(ir-il+1))/log(2.0));
m=max( m, max(mf[il][k], mf[ir-(1<<k)+1][k]));
return m;
}
}
int main()
{
int i,N,Q,l,r;
while(scanf("%d", &N)!=EOF && N)
{
scanf("%d", &Q);
memset(f, 0, sizeof(f));
for(a[0]=0,i=1, n=0; i<=N; i++)
{
scanf("%d", a+i);
if(a[i]!=a[i-1])
index[ a[i] ]=++n, start[n]=i;
f[n]++;
}
rmq_init();
for(i=0; i<Q; i++)
{
scanf("%d%d", &l, &r);
printf("%d\n", rmq(l,r));
}
}
return 0;
}
posted @
2010-03-27 14:50 wyiu 閱讀(442) |
評論 (1) |
編輯 收藏
跑了8616K 2016MS，相當慢，不知道大牛怎么跑3、400MS左右
#include <iostream>
#include <math.h>
using namespace std;
int mx[50001][21];
int mi[50001][21];
int d[50001];
int n;
void rmq_init()
{
int i,j;
for(i=1;i<=n;i++) { mx[i][0]=d[i]; mi[i][0]=d[i]; }
int m=floor(log((double)n)/log(2.0));
for(i=1;i<=m;i++)
for(j=0;j+(1<<(i-1))<=n;j++)
{
mx[j][i]=max(mx[j][i-1],mx[j+(1<<(i-1))][i-1]);
mi[j][i]=min(mi[j][i-1],mi[j+(1<<(i-1))][i-1]);
}
}
int rmq(int l,int r)
{
int m=floor(log((double)(r-l+1))/log(2.0));
int a=max(mx[l][m],mx[r-(1<<m)+1][m]);
int b=min(mi[l][m],mi[r-(1<<m)+1][m]);
return a-b;
}
int main()
{
int q,l,r,i;
while(scanf("%d%d", &n, &q)!=EOF)
{
for(i=1; i<=n; i++)
scanf("%d", &d[i]);
rmq_init();
while(q--)
{
scanf("%d%d", &l, &r);
printf("%d\n", rmq(l,r));
}
}
return 0;
}
posted @
2010-03-27 02:07 wyiu 閱讀(232) |
評論 (0) |
編輯 收藏//x從0開始，樹狀數組要求從一開始，故x++
//getsum(x)，求xi<x的star數
//level(sum)++,level為sum的star數++
#include <iostream>
using namespace std;
#define M 32001
int level[32005];//原數組
int c[32005];//樹狀數組
//k&(k^(k-1))
int getsum(int k)
{
int sum;
for(sum=0; k>0; k-=((-k)&k) ) sum+=c[k];
return sum;
}
void modify(int k, int detal) //k:position ,detal:increase value
{
for(; k<=M; k+=((-k)&k) ) c[k]+=detal;
}
int main()
{
int x,y,n,i;
while(scanf("%d", &n)!=EOF)
{
memset(c, 0, sizeof(c));
memset(level, 0, sizeof(level));
for(i=0; i<n; i++)
{
scanf("%d%d", &x, &y);
level[ getsum(++x) ] ++;
modify( x, 1);
}
for(i=0; i<n; i++)
{
printf("%d\n", level[i]);
}
}
return 0;
}
posted @
2010-03-26 22:07 wyiu 閱讀(354) |
評論 (0) |
編輯 收藏#include <iostream>
#include <memory.h>
using namespace std;
#define P 101
#define M 301
bool map[P][M];
int n,m;
int chk[M];
int match[M];
int dfs(int p)
{
int i,t;
for(i=1; i<=m; i++)
if(map[p][i] && !chk[i])
{
chk[i]=1;
t=match[i];
match[i]=p;
if(t==0 || dfs(t)) return 1;
match[i]=t;
}
return 0;
}
int mat()
{
int i, res=0;
for(i=1; i<=n; i++)
{
memset(chk, 0, sizeof(chk));
if(dfs(i)) res++;
}
return res;
}
int main()
{
int i,j,count,mi,kase;
scanf("%d",&kase);
while(kase--)
{
scanf("%d%d",&n, &m);
memset(map, 0, sizeof(map));
memset(match, 0, sizeof(match));
for(i=1; i<=n; i++)
{
scanf("%d",&count);
for(j=1; j<=count; j++)
{
scanf("%d", &mi);
map[i][mi]=1; //map[mi][i]=true;
}
}
if(mat()==n) printf("YES\n");
else printf("NO\n");
}
return 0;
}
posted @
2010-03-25 16:29 wyiu 閱讀(344) |
評論 (0) |
編輯 收藏#include <iostream>
using namespace std;
struct edge
{
int v,next;
};
edge grap[60005];
edge grapt[61005];
int cnt;
int n,m;
bool visit[10005];
int finish[10005], id;
int grp[10005], g;
int outdegree[10005];
void add(int u, int v)
{
grap[cnt].v=v;
grap[cnt].next=grap[u].next;
grap[u].next=cnt;
grapt[cnt].v=u;
grapt[cnt].next=grapt[v].next;
grapt[v].next=cnt;
cnt++;
}
void dfs(int u)
{
int p;
visit[u]=1;
p=grap[u].next;
while(p)
{
if(!visit[grap[p].v])
dfs(grap[p].v);
p=grap[p].next;
}
finish[++id]=u;
}
void dfst(int u)
{
int p;
visit[u]=1;
p=grapt[u].next;
grp[u]=g;
while(p)
{
if(!visit[grapt[p].v])
dfst(grapt[p].v);
p=grapt[p].next;
}
}
void scc()
{
int i;
g=0,id=0;
memset(visit, 0, sizeof(visit));
for(i=1; i<=n; i++)
if(!visit[i])
dfs(i);
memset(visit, 0, sizeof(visit));
for(i=n; i>0 ; --i)
{
if(!visit[finish[i]])
{
g++;
dfst(finish[i]);
}
}
}
void solve()
{
int i,j, p, tmp;
memset(outdegree, 0, sizeof(outdegree));
for(i=1; i<=n; i++)
{
p=grap[i].next;
while(p)
{
if(grp[i]!=grp[ grap[p].v])
++outdegree[grp[i]];
p=grap[p].next;
}
}
for(i=1, tmp=0; i<=g; i++)
{
//printf("%d %d\n", i, outdegree[i]);
if(outdegree[i] == 0)
{
++tmp, j=i;
}
}
//printf("%d %d\n", tmp, j);
if(tmp!=1) // >1 || 0
{
printf("0\n");
}
else
{
tmp=0;
for(i=1; i<=n; i++)
if(grp[i]== j )
tmp++;
printf("%d\n", tmp);
}
}
int main()
{
int i, j, u, v;
while(scanf("%d%d",&n, &m)!=EOF)
{
cnt=n+1;
memset(grap, 0, sizeof(grap));
memset(grapt, 0, sizeof(grapt));
for(i=0; i<m; i++)
{
scanf("%d%d", &u, &v);
add(u, v);
}
scc();
solve();
}
return 0;
}
posted @
2010-03-25 16:28 wyiu 閱讀(229) |
評論 (0) |
編輯 收藏#include <iostream>
using namespace std;
#define N 301
#define M 96
bool map[N][M];
int match[M];
bool chk[M];
int n, m=85;
int dfs(int p)
{
int i,t;
for(i=1; i<=m; i++)
{
if(!chk[i] && map[p][i] )
{
chk[i]=1;
t=match[i];
match[i]=p;
if(t == -1 || dfs(t) ) return 1;
match[i]=t;
}
}
return 0;
}
int maxMah()
{
int i, ans=0;
for(i=1; i<=n; i++)
{
memset(chk, 0, sizeof(chk));
if(dfs(i)) ans++;
}
return ans;
}
int main()
{
int i,j,p,q,t;
while(scanf("%d", &n)!=EOF)
{
//printf("%d\n",n);
memset(map,0, sizeof(map));
memset(match, -1, sizeof(match));
for(i=1; i<=n; i++)
{
//printf("%d\n",i);
scanf("%d", &t);
//printf("%d\n", t);
for(j=0; j<t; j++)
{
scanf("%d%d",&p, &q);
map[i][(p-1)*12+q]=1;
}
}
printf("%d\n",maxMah());
}
return 0;
}
posted @
2010-03-25 16:26 wyiu 閱讀(376) |
評論 (0) |
編輯 收藏
#define setbit(x,y) x|=(1<<(y)) //將X的第Y位置1
#define clrbit(x,y) x&=~(1<<(y)) //將X的第Y位清0
...個人菜B做法：
#include <iostream>
using namespace std;
unsigned r,rp,x,y;
unsigned a[32]={0xfffffffe,0xfffffffd,0xfffffffb,0xfffffff7,
0xffffffef,0xffffffdf,0xffffffbf,0xffffff7f,
0xfffffeff,0xfffffdff,0xfffffbff,0xfffff7ff,
0xffffefff,0xffffdfff,0xffffbfff,0xffff7fff,
0xfffeffff,0xfffdffff,0xfffbffff,0xfff7ffff,
0xffefffff,0xffdfffff,0xffbfffff,0xff7fffff,
0xfeffffff,0xfdffffff,0xfbffffff,0xf7ffffff,
0xefffffff,0xdfffffff,0xbfffffff,0x7fffffff,};
int main()
{
while(scanf("%x,%d,%d", &r, &x, &y)!=EOF)
{
printf("%x\n",(((r&a[x])|(1<<y))|(1<<(y-1)))&a[y-2]);
}
return 0;
}
posted @
2010-03-25 15:50 wyiu 閱讀(359) |
評論 (0) |
編輯 收藏
#include <iostream>
using namespace std;
#define N 1100
#define M 1100
bool map[N][M];
int match[M];
bool chk[M];
int n, m;
bool num[1100];
int hash[1100];
int dfs(int p)
{
int i,t;
for(i=1; i<=m; i++)
{
if(!chk[i] && map[p][i] )
{
chk[i]=1;
t=match[i];
match[i]=p;
if(t == -1 || dfs(t) ) return 1;
match[i]=t;
}
}
return 0;
}
int maxMah()
{
int i, ans=0;
for(i=1; i<=n; i++)
{
memset(chk, 0, sizeof(chk));
if(dfs(i)) ans++;
}
return ans;
}
int getnum(char *s)
{
int i,ret=0, l=strlen(s);
for(i=0; s[i]; i++)
{
ret+= (s[i]=='1'?(1<<(l-i-1)):0);
}
return ret;
}
int main()
{
int x,y, i, j, k, c;//,ans=0;
char tmp[15];
while(scanf("%d%d", &x, &y)!=EOF && x!=0 && y!=0 )
{
memset(map, 0, sizeof(map));
memset(num,0, sizeof(num));
memset(hash,0, sizeof(hash));
memset(match, -1, sizeof(match));
for(i=0; i<y; i++)
{
scanf("%s",tmp);
for(j=0; tmp[j]; j++)
if(tmp[j]=='*')
break;
if(tmp[j])
{
tmp[j]='0';
num[ getnum(tmp) ] =true ;
tmp[j]='1';
num[ getnum(tmp) ] =true ;
}
else num[ getnum(tmp) ] =true ;
}
for(i=0, k=0; i<(1<<x); i++)
if(num[i])
{
hash[++k]=i;
}
for(i=1; i<=k; i++)
for(j=1; j<=k; j++)
{
c=hash[i]^hash[j];//判是否相差一位
if(c && ((c&(c-1))==0) )//判是否相差一位
map[i][j]=map[j][i]=1;
}
n=m=k;
printf("%d\n",k-maxMah()/2); //(k-maxMah)+maxMah/2=k-maxMah()/2
}
return 0;
}
posted @
2010-03-25 01:23 wyiu 閱讀(471) |
評論 (0) |
編輯 收藏#include<iostream>
using namespace std;
int x[4];
int y[4];
int gcd(int a,int b)
{
if(b==0) return a;
else return gcd(b,a%b);
}
int main()
{
int area;
int b,i;
while(scanf("%d%d%d%d%d%d",x+1,y+1,x+2,y+2,x+3,y+3)!=EOF)
{
if(x[1]==0 && y[1]==0
&& x[2]==0 && y[2]==0
&& x[3]==0 && y[3]==0 ) break;
area=abs( (x[2]-x[1])*(y[3]-y[1])-(x[3]-x[1])*(y[2]-y[1]) );
b=gcd(abs(x[2]-x[1]),abs(y[2]-y[1]))+gcd(abs(x[3]-x[2]),abs(y[3]-y[2]))+gcd(abs(x[1]-x[3]),abs(y[1]-y[3]));
i=(area+2-b)>>1;
printf("%d\n",i);
}
return 0;
}
posted @
2009-10-06 18:28 wyiu 閱讀(125) |
評論 (0) |
編輯 收藏