[JSOI]Word Query电子字典

[JSOI]Word Query电子字典

Time Limit:10000MS  Memory Limit:65536K
Total Submit:27 Accepted:11
Case Time Limit:1000MS

Description

人们在英文字典中查找某个单词的时候可能不知道该单词的完整拼法,而只知道该单词的一个错误的近似拼法,这时人们可能陷入困境,为了查找一个单词而浪费大 量的时间。带有模糊查询功能的电子字典能够从一定程度上解决这一问题:用户只要输入一个字符串,电子字典就返回与该单词编辑距离最小的几个单词供用户选 择。
字符串a与字符串b的编辑距离是指:允许对a或b串进行下列“编辑”操作,将a变为b或b变为a,最少“编辑”次数即为距离。
 删除串中某个位置的字母;
 添加一个字母到串中某个位置;
 替换串中某一位置的一个字母为另一个字母;

JSOI团队正在开发一款电子字典,你需要帮助团队实现一个用于模糊查询功能的计数部件:对于一个待查询字符串,如果它是单词,则返回-1;如果 它不是单词,则返回字典中有多少个单词与它的编辑距离为1。

Input

第一行包含两个正整数N (N < = 10,000)和M (M < = 10,000)。
接下来的N行,每行一个字符串,第i + 1行为单词Wi。单词长度在1至20之间。再接下来M行,每行一个字符串,第i + N + 1表示一个待查字符串Qi。待查字符串长度在1至20之间。Wi和Qi均由小写字母构成,文件中不包含多余空格。所有单词互不相同,但是查询字符串可能有 重复。

提示:有50%的数据范围:N < = 1,000,M < = 1,000。

Output

输出应包括M行,第i行为一个整数Xi。Xi = -1表示Qi为字典中的单词;否则Xi表示与Qi编辑距离为1的单词的个数。

Sample Input

4 3
abcd
abcde
aabc
abced
abcd
abc
abcdd

Sample Output

-1
2
3

Hint

abcd在单词表中出现过;abc与单词abcd、aabc的编辑距离都是1;abcdd与单词abcd、abcde、abced的编辑距离都是1。

Source

JSOI第二轮Contest1
61.187.179.132:8080/JudgeOnline/showproblem
额。这题目告诉我一件事情就是unsigned long long基本是不会冲突的,所以可以放心的用Hash。。直接暴力Hash了,replace的模拟是枚举每一个位置,然后枚举改变成什么,相应的在原串的Hash值+上改变量。效率是(26*Len),
delete和Insert首先要算出从一个位置到数字首和数字尾的Hash值,然后Delete枚举位置删除就可以了,Insert还要枚举插入那个数。
总共就是(26*Len*m+Len*n)。。。速度虽然慢,还是A掉了(*^__^*)
囧。。为什么别人的程序都是20000KB+的我这个只有500而且还这么慢,悲剧。。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#include<set>
#define rep(i,n) for(int i=0;i<n;i++)
#define For(i,l,r) for(int i=l;i<=r;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1;
const int seed=131,maxl=20+10;
typedef unsigned long long ull;
struct Hash
{
static const int size=17771;
struct node
{
ull key;
int num;
node*next;
node(ull _key,int _num,node*_n):key(_key),num(_num),next(_n){}
}*H[size];
Hash(){memset(H,0,sizeof(H));}
int find(ull code)
{
int h=code%size;
for(node*i=H[h];i;i=i->next)if(i->key==code)return i->num;
return -1;
}
void insert(ull code,int num)
{
//cout<<"I"<<code<<endl;
int h=code%size;
H[h]=new node(code,num,H[h]);
}
}hash;
ull Code(char*s)
{
ull ret=0;
while(*s) ret*=seed,ret+=*(s++);
return ret;
}
int n,m;
void solve()
{
static ull Power[maxl];
char s[maxl];
Power[0]=1;
For(i,1,maxl-1)Power[i]=Power[i-1]*seed;
scanf("%d %d",&n,&m);
rep(i,n) scanf("%sn",s),hash.insert(Code(s),i);
ull Left[maxl],Right[maxl];
while(m–)
{
scanf("%sn",s);ull t=Code(s),x,ret=0,l=strlen(s),tmp;
set<int> S;
if(hash.find(t)!=-1){printf("-1n");continue;}
//Replace a letter
for(int i=0;i<l;i++)
{
for(char c=’a';c<=’z';c++)if(c!=s[i])
if((tmp=hash.find(t+Power[l-i-1]*(c-s[i])))!=-1)
S.insert(tmp);
}
//Cal the Left Hash value and the Right Hash value
Left[0]=0;
for(int i=1;i<=l;i++)
Left[i]=Left[i-1]*seed+s[i-1];
Right[l+1]=0;
for(int i=l;i>=1;i–)
Right[i]=Right[i+1]+Power[l-i]*s[i-1];
//Delete a letter
for(int i=1;i<=l;i++)
{
ull x=Left[i-1]*Power[l-i]+Right[i+1];
if((tmp=hash.find(x))!=-1)S.insert(tmp);//cout<<"D"<<endl;
}
//Insert a letter
for(int i=0;i<=l;i++)
{
ull x=Left[i]*Power[l-i+1]+Right[i+1];
for(char c=’a';c<=’z';c++)if((tmp=hash.find(x+Power[l-i]*c))!=-1)S.insert(tmp);//cout<<"I"<<endl;
}
printf("%dn",S.size());
}
}
int main()
{
//freopen("in","r",stdin);
solve();
}

USACO Betsy’s Tour

额。。这题过的有点悬
USER: Tom Chen [45384401]
TASK: betsy
LANG: C++

Compiling…
Compile: OK

Executing…
Test 1: TEST OK [0.011 secs, 2804 KB]
Test 2: TEST OK [0.000 secs, 2804 KB]
Test 3: TEST OK [0.011 secs, 2804 KB]
Test 4: TEST OK [0.011 secs, 2804 KB]
Test 5: TEST OK [0.000 secs, 2804 KB]
Test 6: TEST OK [0.022 secs, 2804 KB]
Test 7: TEST OK [0.961 secs, 2804 KB]

All tests OK.
时间卡的好紧额囧。。
我只用了两个剪枝,一个是每个除了终点之外的点要一进一出所以要记录相邻的点数,还有一个就是当前点到终点的距离如果小于剩下的点数就剪枝。。
这样都能过囧。。
Code:
/*
PROG: betsy
LANG: C++
ID: Tom Chen
*/
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define For(i,l,r) for(int i=l;i<=r;i++)
#define pb push_back
using namespace std;
const int maxn=10,di[]={1,0,-1,0},dj[]={0,-1,0,1};
bool vis[maxn][maxn]={0};
int n,ans=0;
int C[maxn][maxn];
int ii,jj;
void show()
{
rep(i,n)
{
rep(j,n) cout<<C[i][j]<<" ";
cout<<endl;
}
}
int Put(int i,int j)
{
int ret=0;
vis[i][j]=true;
rep(d,4)
{
ii=di[d]+i,jj=dj[d]+j;
if(!vis[ii][jj]&&–C[ii][jj]<2&&(ii!=n||jj!=1))
ret++;
}
return ret;
}
void Back(int i,int j)
{
vis[i][j]=false;
rep(d,4)
{
ii=di[d]+i,jj=dj[d]+j;
if(!vis[ii][jj])
++C[ii][jj];
}
}
inline int dist(int a,int b){return a>0?a:-a+b>0?b:-b;}
void dfs(int i,int j,int c)
{
//cout<<i<<" "<<j<<" "<<c<<endl;
//show();
if(n*n-c<dist(i-n,j-1))return;
if(i==n&&j==1)
{
if(c==n*n) ans++;
return;
}
int t=Put(i,j);
if(t<=1)
{
rep(d,4)
{
ii=i+di[d],jj=j+dj[d];
if(!vis[ii][jj]&&(!t||C[ii][jj]<2))
dfs(ii,jj,c+1);
}
}
Back(i,j);
}
int main()
{
freopen("betsy.in","r",stdin);
freopen("betsy.out","w",stdout);
cin>>n;
rep(i,n+2)rep(j,n+2)vis[i][j]=true;
For(i,1,n)For(j,1,n) C[i][j]=4,vis[i][j]=false;
For(i,1,n) C[i][1]=C[1][i]=C[n][i]=C[i][n]=3;
C[1][1]=C[1][n]=C[n][1]=C[n][n]=2;
dfs(1,1,1);
cout<<ans<<endl;
}

Vijos 香樟树

额。。VIJOS复活了。。所以我去A了这道题。。www.vijos.cn/Problem_Show.asp
题目是说给你n个数,都小于10^5,然后让你求出其中一个子序列(连不连续无所谓,只要顺序是原序列的顺序就OK)。。 相邻两个数不互质。。让你求这个序列的最大长度。。n<=100000
很明显暴力DP是会悲剧的,如果你用Dpi表示第i个数结尾的最长长度然后O(n)枚举前一个的话是O(n^2)的。关键是利用题目的性质。
注意到不互质的数一定有一个公共的质因子,就简单了。首先算出10^5一下每个质数,然后开个数组保存每个当前以第i个质数的倍数结尾的数列的最长值,然 后对于每个数枚举他的每个质因子计算并更新一下就可以了。。
关键是一个数的质因子数目显然是O(logn)级别的,并且预先处理也可以大大降低枚举量。。我感觉应该会很快,没想到0ms秒杀,爽额。。
Code:
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1,maxn=100000+1,maxp=maxn>>3;
bool NotPrime[maxn]={0};
int Ps[maxp],cnt=0;
void GetPrime()
{
for(int i=2;i*i<maxn;i++)
{
if(!NotPrime[i])
{
for(int j=i*2;j<maxn;j+=i)
NotPrime[j]=true;
}
}
for(int i=2;i<maxn;i++)
if(!NotPrime[i])
Ps[cnt++]=i;
}
int Max[maxp],pnt,Tmp[1000];
void GetDiv(int p)
{
pnt=0;
for(int i=0;i<cnt;i++)
{
int t=Ps[i];if(t*t>p)break;
if(p%t==0)
{
Tmp[pnt++]=i;
while(p%t==0)p/=t;
}
}
if(p!=1)
{
int i=lower_bound(Ps,Ps+cnt,p)-Ps;
Tmp[pnt++]=i;
}
}
void solve()
{
int n,x;scanf("%d",&n);
while(n–)
{
scanf("%d",&x);
GetDiv(x);
int ret=0;
rep(i,pnt)ret=max(ret,Max[Tmp[i]]);
ret++;
rep(i,pnt) Max[Tmp[i]]=ret;
}
int ans=0;
rep(i,cnt) ans=max(ans,Max[i]);
printf("%dn",ans);
}
int main()
{
//freopen("in","r",stdin);
GetPrime();
solve();
}

[HAOI2008]硬币购物

[HAOI2008]硬币购物

Time Limit:10000MS Memory Limit:165536K
Total Submit:11 Accepted:8
Case Time Limit:1000MS

Description

硬币购物
一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西,去了tot次。
每次带di枚ci硬币,买si的价值的东西。请问每次有多少种付款方法。

Input

第一行
c1,c2,c3,c4,tot
下面tot行
d1,d2,d3,d4,s

Output

每次的方法数

Sample Input

Sample Output

Source
这题有点NB的,DP+容斥原理囧。。
Code:

#include<iostream>using namespace std;const int maxn=4,maxs=100000+1;typedef long long ll;ll Dp[maxs]={0};int C[maxn];void Cal(){ Dp[0]=1; for(int i=0;i<maxn;i++) for(int j=C[i];j<maxs;j++) Dp[j]+=Dp[j-C[i]];}int D[maxn];void dfs(int p,int ch,int now,ll&ret){ if(now<0) return; if(p==maxn) { if(ch&1) ret-=Dp[now]; else ret+=Dp[now]; return; } dfs(p+1,ch+1,now-C[p]*(D[p]+1),ret); dfs(p+1,ch,now,ret);}void solve(){ int s;ll ans=0;for(int i=0;i<maxn;i++)cin>>D[i]; cin>>s; dfs(0,0,s,ans); cout<<ans<<endl;}int main(){ //freopen("in","r",stdin); int t; for(int i=0;i<maxn;i++)cin>>C[i];cin>>t; Cal(); while(t–)solve();}427数据规模di,s<=100000tot<=10001 2 5 10 23 2 3 1 101000 2 2 2 900

[CQOI2009]dance跳舞

[CQOI2009]dance跳舞

Time Limit:10000MS Memory Limit:165536K
Total Submit:35 Accepted:19
Case Time Limit:1000MS

Description

一次舞会有n个男孩和n个女孩。每首曲子开始时,所有男孩和女孩恰好配成n对跳交谊舞。每个男孩都不会和同一个女孩跳两首(或更多)舞曲。
有一些男孩女孩相互喜欢,而其他相互不喜欢(不会“单向喜欢”)。每个男孩最多只愿意和k个不喜欢的女孩跳舞,而每个女孩也最多只愿意和k个不喜欢的男孩跳舞。
给出每对男孩女孩是否相互喜欢的信息,舞会最多能有几首舞曲?

Input

第一行包含两个整数n和k。以下n行每行包含n个字符,其中第i行第j个字符为’Y’当且仅当男孩i和女孩j相互喜欢。

Output

仅一个数,即舞曲数目的最大值。

Sample Input

Sample Output

Hint

N<=50
K<=30

Source
网络流建模真是越来越得心应手了(*^__^*) 。。这道题目很显然是要最优转判定的,比如判定能不能有T轮,怎么转呢,对每个男生建立3个定点表示全体,得到喜欢的,得到不喜欢的,那么源向全体连一条容量为T的边,全体向喜欢的连无穷大的边,全体向不喜欢的连容量为k的bian,然后女生也类似分为3个跟汇连,然后男生用喜欢节点向喜欢的女生的喜欢节点,用不喜欢节点向不喜欢的女生的不喜欢节点连容量为1连边。。就OK了。。
Code:

#include<cstdio>#include<queue>#include<algorithm>#include<iostream>#define rep(i,n) for(int i=0;i<n;i++)using namespace std;const int maxn=300+20;struct Edge{ int t,c; Edge(int _t,int _c,Edge* _next): t(_t),next(_next),c(_c){} Edge*next,*op;}*E[maxn]={0};int n,vs,vt;int h[maxn],vh[maxn],v;void InsEdge(int s,int t,int c){ //cout<<s<<" "<<t<<" "<<c<<endl; E[s]=new Edge(t,c,E[s]); E[t]=new Edge(s,0,E[t]); E[s]->op=E[t];E[t]->op=E[s];}const int All=0,Like=1,DontLike=2,inf=1<<20;inline int Boy(int x,int type){return x*3+type;}inline int Girl(int x,int type){return (n+x)*3+type;}void Init(){ int k;char x; scanf("%d %dn",&n,&k); v=n*6+2;vs=v-1;vt=v-2; rep(i,n)rep(j,n) { scanf("%cn",&x); int t=x==’Y’?Like:DontLike; InsEdge(Boy(i,t),Girl(j,t),1); } rep(i,n) { InsEdge(vs,Boy(i,All),0); InsEdge(Boy(i,All),Boy(i,Like),inf); InsEdge(Boy(i,All),Boy(i,DontLike),k); InsEdge(Girl(i,All),vt,0); InsEdge(Girl(i,Like),Girl(i,All),inf); InsEdge(Girl(i,DontLike),Girl(i,All),k); }}int aug(int no,int m){ if(no==vt) return m; int l=m; for(Edge*i=E[no];i;i=i->next)if(i->c&&h[no]==h[i->t]+1) { int d=aug(i->t,min(l,i->c)); i->c-=d,i->op->c+=d,l-=d; if(!l||h[vs]>=v) return m-l; } int minh=v; for(Edge*i=E[no];i;i=i->next)if(i->c) minh=min(minh,h[i->t]+1); if(!–vh[h[no]]) h[vs]=v; vh[h[no]=minh]++; return m-l;}int CalFlow(){ memset(h,0,sizeof(h)); memset(vh,0,sizeof(vh)); vh[0]=v;int flow=0; while(h[vs]<v) flow+=aug(vs,inf); return flow;}void Work(){ int Flow=0; for(int i=1;;i++) { for(Edge*e=E[vs];e;e=e->next)e->c++; for(Edge*e=E[vt];e;e=e->next)e->op->c++; Flow+=CalFlow(); if(Flow!=i*n) { cout<<i-1<<endl; break; } }}int main(){ //freopen("in","r",stdin); Init(); Work();}33 0YYYYYYYYY

[AHOI2006]上学路线route

很显然首先spfa出最短路,然后就按最短路建图,然后很显然就换成了最小割的问题了囧。。不过这里的割是有向的,注意一下哦(*^__^*) 嘻嘻
Code:

#include<cstdio>#include<queue>#include<algorithm>#include<iostream>using namespace std;const int maxn=500;struct Edge{ int t,c,Len; bool e; Edge(int _t,int _Len,int _c,Edge* _next): t(_t),Len(_Len),next(_next),c(_c),e(false){} Edge*next,*op; /*void addFlow(int _c) { c-=_c; op->c+=_c; }*/}*E[maxn];int n,m,vs,vt;void InsEdge(int s,int t,int c,int Len){ E[s]=new Edge(t,Len,c,E[s]); E[t]=new Edge(s,Len,c,E[t]); E[s]->op=E[t];E[t]->op=E[s];}void Init(){ scanf("%d %d",&n,&m);int s,t,Len,c; vs=0,vt=n-1; while(m–) { scanf("%d %d %d %d",&s,&t,&Len,&c); InsEdge(s-1,t-1,c,Len); }}const int inf=~0U>>2;int DistToStart[maxn],DistToEnd[maxn];void Spfa(int Dist[maxn],int vs){ queue<int> Q; bool inQ[maxn]={0}; for(int i=0;i<n;i++) Dist[i]=inf; Dist[vs]=0;inQ[vs]=true;Q.push(vs); while(Q.size()) { int t=Q.front();Q.pop();inQ[t]=false;int cost=Dist[t]; for(Edge*i=E[t];i;i=i->next) { int ncost=cost+i->Len; if(ncost<Dist[i->t]) { Dist[i->t]=ncost; if(!inQ[i->t]) inQ[i->t]=true,Q.push(i->t); } } }}void BuildGraph(){ Spfa(DistToStart,vs); Spfa(DistToEnd,vt); int cost=DistToStart[vt]; for(int i=0;i<n;i++) for(Edge*e=E[i];e;e=e->next) if(DistToStart[i]+e->Len+DistToEnd[e->t]==cost) { e->e=true; e->op->e=true; e->op->c=0; } cout<<cost<<endl;}int h[maxn],vh[maxn],v;int aug(int no,int m){ if(no==vt) return m; int l=m; for(Edge*i=E[no];i;i=i->next)if(i->e&&i->c&&h[no]==h[i->t]+1) { int d=aug(i->t,min(l,i->c)); i->c-=d,i->op->c+=d,l-=d; if(!l||h[vs]>=v) return m-l; } int minh=v; for(Edge*i=E[no];i;i=i->next)if(i->e&&i->c) minh=min(minh,h[i->t]+1); if(!–vh[h[no]]) h[vs]=v; vh[h[no]=minh]++; return m-l;}long long CalFlow(){ memset(h,0,sizeof(h)); memset(vh,0,sizeof(vh)); v=n;vh[0]=v;long long flow=0; while(h[vs]<v) flow+=aug(vs,inf); return flow;}int main(){ //freopen("in","r",stdin); Init(); BuildGraph(); cout<<CalFlow()<<endl;}

[SCOI2005]最大子矩阵

[SCOI2005]最大子矩阵

Time Limit:10000MS Memory Limit:165536K
Total Submit:26 Accepted:13
Case Time Limit:1000MS

Description

这里有一个n*m的矩阵,请你选出其中k个子矩阵,使得这个k个子矩阵分值之和最大。注意:选出的k个子矩阵不能相互重叠。

Input

第一行为n,m,k(1≤n≤100,1≤m≤2,1≤k≤10),接下来n行描述矩阵每行中的每个元素的分值(每个元素的分值的绝对值不超过32767)。

Output

只有一行为k个子矩阵分值之和最大为多少。

Sample Input

Sample Output

Source
这个明显要DP,一维的太水就不说了。
二维的话,首先预处理出子矩阵的和比较方便。
设Dp(i,a1,a2)为i个矩形,第1列1..a1,第二列1..a2的最大价值,
那么如果第一列的a1不放的话,是Dp(i,a1-1,a2)。。。
如果第二列的a2不放的话,是Dp(i,a1,a2-1)。。。
如果放的话枚举上一个状态是O(n)的。
然后只有在a1==a2的时候才枚举宽度为2的矩阵的情况就可以了。。
不过细节很要紧,我WA了半天,这样下去怎么行啊。比赛考到的话肯定悲剧的囧。。
Code:

#include<iostream>#include<cstring>using namespace std;const int maxn=100+10,maxk=10+1,inf=~0U>>2;int n,m,k;//solve 1inline void Renew(int&x,int c){ x=max(x,c);}void Solve1(){ int Dp[maxk][maxn]={0}; int A[maxn]={0}; for(int i=1;i<=n;i++)cin>>A[i],A[i]+=A[i-1]; for(int i=1;i<=k;i++) { for(int j=0;j<=n;j++) { int&x=Dp[i][j];x=-inf; if(j)x=Dp[i][j-1]; for(int o=0;o<j;o++) { Renew(x,Dp[i-1][o]+A[j]-A[o]); } } } cout<<Dp[k][n]<<endl;}//solve 2void Solve2(){ int Dp[maxk][maxn][maxn]={0}; int A[2][maxn]={0},S[maxn]={0}; for(int j=1;j<=n;j++) for(int i=0;i<2;i++) cin>>A[i][j],S[j]+=A[i][j],A[i][j]+=A[i][j-1]; for(int j=1;j<=n;j++) S[j]+=S[j-1]; for(int i=1;i<=k;i++) for(int a1=0;a1<=n;a1++) for(int a2=0;a2<=n;a2++) { int&x=Dp[i][a1][a2];x=-inf; if(a1) { Renew(x,Dp[i][a1-1][a2]); for(int o=0;o<a1;o++) Renew(x,Dp[i-1][o][a2]+A[0][a1]-A[0][o]); } if(a2) { Renew(x,Dp[i][a1][a2-1]); for(int o=0;o<a2;o++) Renew(x,Dp[i-1][a1][o]+A[1][a2]-A[1][o]); } if(a1==a2) { for(int o=0;o<a1;o++) Renew(x,Dp[i-1][o][o]+S[a1]-S[o]); } } cout<<Dp[k][n][n]<<endl;}int main(){ //freopen("in","r",stdin); cin>>n>>m>>k; if(m==1)Solve1(); else Solve2();}93 2 21 -32 3-2 3

[HNOI2005]虚拟内存

[HNOI2005]虚拟内存

Time Limit:50000MS Memory Limit:165536K
Total Submit:16 Accepted:6
Case Time Limit:5000MS

Description

操作系统中一种重要的存储管理技术就是虚拟内存技术。操作系统中允许进程同时运行,也就是并行。每个进程都有其相对独立的数据块(进程运行的过程中将对其进行读写操作)。理想的情况下,这些数据块都应该存放在内存中,这样才能实现高效的读写操作。但事实上,内存的容量有限,每个进程只能把一部分数据放在内存中,为了解决这个矛盾,提出了虚拟内存技术。
虚拟内存技术的基本原理是:对进程而言,内存空间是无限大的,进程可以随意地读写数据,而对操作系统内部而言,利用外存来模拟扩充的内存空间,进程要求访问某个内存单元时,交由操作系统处理,操作系统首先在内存中查找该单元是否存在,如果存在,查找成功,否则转入外存查找(一定存在于外存中)。
就存储介质的物理性质而言,内存的访问速度相对于外存要快得多,因此对于每个进程来说操作系统应该把那些访问次数较多的数据存放在内存中,而把那些访问次数很少的数据放在外存中。如何选择内存中暂留的数据是一个很值得研究的问题,下面介绍一个内存管理中比较常用的算法:
内存中的数据以页为基本存储单位,进程的读写操作都针对页来进行。实际内存空间被分割成n页,虚拟内存空间的页数往往要多得多。某一时刻,进程需要访问虚存编号为P的页,该算法的执行步骤如下:
a. 首先在内存中查找,如果该页位于内存中,查找成功,转d,否则继续下面的操作;
b. 寻找内存中是否存在空页(即没有装载任何数据页的页面),若有,则从外存中读入要查找页,并将该页送至内存中的空页进行存储,然后转d,否则继续下面的操作;
c. 在内存中寻找一个访问次数最少的页面(如果存在多个页面的访问次数同时为最少,则选取最早读入数据进入内存的那个页面),从外存中读入要查找页,替换该页。
d. 结束
所谓访问次数是指从当前页面进入内存到该时刻被访问的次数,如果该页面以前进入过内存并被其它页面替换,那么前面的访问次数不应计入这个时刻的访问次数中。
你的任务是设计一个程序实现上述算法。
测试数据将会提供m条读写内存的命令,每条命题提供要求访问的虚拟内存页的编号P。你的程序要求能够模拟整个m条命令的全部执行过程,所有的命令是按照输入的先后执行的,最开始的时候内存中的n页全为空。

Input

第1行为n<10000和m<1000000,分别表示内存页数和读写内存命令条数。接下来有m行,其中第i+1行有一个正整数Pi<=10^9,表示第i条读写内存命令需要访问的虚拟内存页的编号。

Output

仅包含一个正整数,表示在整个模拟过程中,在内存中直接查找成功的次数(即上面的算法只执行步骤a的次数)。

Sample Input

Sample Output

Source
很显然是一个模拟题。。
饿。这个应该用一个Hash查找id,用一个Heap保存当前内存的状态的,但我直接用了map,结果慢死囧。。
Code:

#include<cstdio>#include<set>#include<map>#include<utility>#include<queue>#include<iostream>using namespace std;typedef pair<int,int> ii;struct state{ int used,first; bool inQ; state(){} state(int _first):used(1),first(_first),inQ(true){}};map<int,state> id;struct node{ int id,used,first; node(const state&s,int _id) { used=s.used;first=s.first; id=_id; } bool operator<(const node&o)const { if(used!=o.used) return o.used<used; return o.first<first; }};int n,m,Time=0,ans=0;priority_queue<node> Q;void Check(){ while(Q.size()>=n) { node t=Q.top();Q.pop(); if(t.used<id[t.id].used) { t.used=id[t.id].used; Q.push(t); } else { state&s=id[t.id]; s.inQ=false; s.used=1; //cout<<"Out"<<t.id<<endl; break; } }}void Insert(int x){ if(id.count(x)) { state&s=id[x]; if(s.inQ) { //cout<<"Great"<<x<<endl; ans++;s.used++;s.first=Time; } else { Check();s.inQ=true;s.first=Time; Q.push(node(s,x)); } } else { state s(Time); id[x]=s; Check(); Q.push(node(s,x)); } //cout<<"In"<<x<<endl;}int main(){ freopen("in","r",stdin); scanf("%d %d",&n,&m);int x; while(m–) { scanf("%d",&x); Insert(x); ++Time; } cout<<ans<<endl;}

Code:

13 8 11234254

[Ahoi2009]chess 中国象棋

[Ahoi2009]chess 中国象棋

Time Limit:10000MS Memory Limit:65536K
Total Submit:21 Accepted:11
Case Time Limit:1000MS

Description

在N行M列的棋盘上,放若干个炮可以是0个,使得没有任何一个炮可以攻击另一个炮。
请问有多少种放置方法,中国像棋中炮的行走方式大家应该很清楚吧.

Input

一行包含两个整数N,M,中间用空格分开.

Output

输出所有的方案数,由于值比较大,输出其mod 9999973

Sample Input

Sample Output

Hint

除了在3个格子中都放满炮的的情况外,其它的都可以.

100%的数据中N,M不超过100
50%的数据中,N,M至少有一个数不超过8
30%的数据中,N,M均不超过6

Source

Day2
61.187.179.132:8080/JudgeOnline/showproblem
要Dp。。非常的复杂,看Code吧。。累死了。。
Code:

#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<cstdlib>#include<cstring>#include<string>#include<vector>#include<set>#include<queue>#include<map>#define rep(i,n) for(int i=0;i<n;i++)#define For(i,a,b) for(int i=a;i<=b;i++)#define tr(i,x) for(typeof(x.begin()) i=x.begin();i!=x.end();i++)#define all(x) x.begin(),x.end()#define pb push_backusing namespace std;const int inf=~0U>>1;typedef vector<int> vi;typedef vector<vi> vvi;typedef pair<int,int> ii;const int maxn=100+10,mod=9999973;int Dp[2][maxn][maxn],n,m;int C[maxn][maxn]={0};int plus_mod(int&a,int b){ a+=b;return a%=mod;}int multi_mod(int&a,int b){ return a=((long long)a*b)%mod;}void GetC(){ C[0][0]=1; for(int i=1;i<=m;i++) { C[i][0]=C[i][i]=1; for(int j=1;j<i;j++) { C[i][j]=C[i-1][j-1]+C[i-1][j]; C[i][j]%=mod; } }}#define MM(x) memset(x,0,sizeof(x))int main(){ cin>>n>>m;int now=0,next=1; MM(Dp);GetC(); Dp[next][m][0]=1; for(int i=0;i<n;i++) { swap(now,next); MM(Dp[next]); for(int a0=0;a0<=m;a0++) for(int a1=0;a1+a0<=m;a1++) if(Dp[now][a0][a1]) { int x=Dp[now][a0][a1],c; //Dont used Row i plus_mod(Dp[next][a0][a1],x); //Put one if(a0) { c=x; multi_mod(c,C[a0][1]); plus_mod(Dp[next][a0-1][a1+1],c); } if(a1) { c=x; multi_mod(c,C[a1][1]); plus_mod(Dp[next][a0][a1-1],c); } //Put two if(a0>=2) { c=x; multi_mod(c,C[a0][2]); plus_mod(Dp[next][a0-2][a1+2],c); } if(a1>=2) { c=x; multi_mod(c,C[a1][2]); plus_mod(Dp[next][a0][a1-2],c); } if(a0&&a1) { c=x; multi_mod(c,C[a0][1]); multi_mod(c,C[a1][1]); plus_mod(Dp[next][a0-1][a1],c); } } } int ans=0; rep(i,m+1)rep(j,m+1)plus_mod(ans,Dp[next][i][j]); cout<<ans<<endl;}71 3

USACO Telecowmunication

我突然很怀念USACO,去年我A的差不多了就不想A了。。这个月把它A完吧(*^__^*)
这个题目大意nocow上有。。不过我的算法完全是错的居然过了囧。。
很明显是一个最小割的问题,关键是要让字典序最小,
一般来说是要一个个边枚举的删过去的,但是我懒得怎么搞,于是我给每个节点的点权改成了10000+i i表示第i个节点,然后就这样做了。。
结果居然AC了。这数据也太烂了囧。。
Code:

/* PROG: telecow LANG: C++ ID: Tom Chen*/#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<cstdlib>#include<cstring>#include<string>#include<vector>#include<set>#include<queue>#include<map>#define rep(i,n) for(int i=0;i<n;i++)#define For(i,a,b) for(int i=a;i<=b;i++)#define tr(i,x) for(typeof(x.begin()) i=x.begin();i!=x.end();i++)#define all(x) x.begin(),x.end()#define pb push_backusing namespace std;const int inf=~0U>>1,maxn=200+10;typedef vector<int> vi;struct Edge{ int t,c; Edge*next,*op; Edge(int _t,int _c,Edge* _next):t(_t),c(_c),next(_next){}}*E[maxn]={0};void InsEdge(int s,int t,int c){ E[s]=new Edge(t,c,E[s]); E[t]=new Edge(s,0,E[t]); E[s]->op=E[t];E[t]->op=E[s];}int vs,vt,n,m;int h[maxn],vh[maxn];const int in=0,out=1,off=10000;inline int node(int x,int type){ return x*2+type;}void Init(){ cin>>n>>m>>vs>>vt;vs–;vt–; vs=node(vs,out); vt=node(vt,in); int s,t; rep(i,n) InsEdge(node(i,in),node(i,out),off+i); while(m–) { cin>>s>>t;–s;–t; InsEdge(node(s,out),node(t,in),inf); InsEdge(node(t,out),node(s,in),inf); }}int v;int aug(int no,int m){ if(no==vt) return m; int l=m; for(Edge*i=E[no];i;i=i->next)if(i->c&&h[no]==h[i->t]+1) { int d=aug(i->t,min(l,i->c)); i->c-=d,i->op->c+=d,l-=d; if(!l||h[vs]>=v) return m-l; } int minh=v; for(Edge*i=E[no];i;i=i->next)if(i->c) minh=min(minh,h[i->t]+1); if(!–vh[h[no]]) h[vs]=v;++vh[h[no]=minh]; return m-l;}int CalFlow(){ memset(h,0,sizeof(h)); memset(vh,0,sizeof(vh)); v=n*2;vh[0]=v;int flow=0; while(h[vs]<v) flow+=aug(vs,inf); return flow;}bool Vis[maxn]={0};void dfs(int x){ Vis[x]=true; for(Edge*i=E[x];i;i=i->next)if(i->c&&!Vis[i->t])dfs(i->t);}bool Used(int x){ if (Vis[node(x,in)]&&!Vis[node(x,out)]) return true; return false;}void Work(){ int flow=CalFlow()/off; cout<<flow<<endl; vi Ans; dfs(vs); rep(i,n)if(Used(i)) Ans.pb(i+1); cout<<Ans[0]; for(int i=1;i<Ans.size();i++) cout<<" "<<Ans[i]; cout<<endl;}int main(){ freopen("telecow.in","r",stdin); freopen("telecow.out","w",stdout); Init(); Work();}

Page 2 of 712345...Last »