[Shoi2007]Setstack 集合堆栈机

[Shoi2007]Setstack 集合堆栈机

Time Limit:1000MS Memory Limit:65536K
Total Submit:22 Accepted:8

Description

Input

Output

Sample Input

Sample Output

Hint

Source

Code：
#include <vector>

#include <stack>
#include <cstdio>
#include <algorithm>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define All(x) x.begin(),x.end()
const int seed=13331;
using namespace std;
typedef unsigned long long ull;
typedef vector<ull> set;
ull Code(const set&s)
{
ull ret=0;
rep(i,s.size())ret*=seed,ret+=s[i]+78;
return ret;
}
void Normal(set&s)
{
sort(All(s));
s.resize(unique(All(s))-s.begin());
}
stack<set> S;
int main()
{
int n;scanf("%d",&n);char cmd[10];set a,b;
while(n–)
{
scanf("%s",cmd);
switch(cmd[0])
{
case ‘P':S.push(set());break;
case ‘D':S.push(S.top());break;
case ‘A':a=S.top();S.pop();b=S.top();S.pop();b.pb(Code(a));
Normal(b);S.push(b);break;
default:a=S.top();S.pop();b=S.top();S.pop();set c(a.size()+b.size());
if(cmd[0]==’U’)c.resize(set_union(All(a),All(b),c.begin())-c.begin());
else c.resize(set_intersection(All(a),All(b),c.begin())-c.begin());
Normal(c);S.push(c);break;
}
printf("%dn",S.top().size());
}
}

001011222

[CQOI2007]余数之和sum

[CQOI2007]余数之和sum

Time Limit:5000MS Memory Limit:165536K
Total Submit:41 Accepted:17
Case Time Limit:1000MS

Description

Input

Output

Sample Input

Sample Output

Hint

50%的数据满足：1<=n, k<=1000
100%的数据满足：1<=n ,k<=10^9

Source

Code：

#include <iostream>using namespace std;typedef long long ll;int main(){ int n,k;cin>>n>>k;ll ans=0; for(int i=1;i<=n;i++) { int a=k/i,l=k/(a+1)+1,r=a?k/a:n; if(r>=n)r=n; ans+=ll(k)*(r-l+1)-ll(a)*(l+r)*(r-l+1)/2; i=r; } cout<<ans<<endl;}75 3

[JSOI2009]火星藏宝图

[JSOI2009]火星藏宝图

Time Limit:5000MS Memory Limit:65536K
Total Submit:38 Accepted:17
Case Time Limit:1000MS

Description

Input

Output

Sample Input

Sample Output

Hint

Source

JSOI2009Day2

Code：

#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>#define rep(i,n) for(int i=0;i<n;i++)using namespace std;const int maxn=1000,maxm=200000,inf=~0U>>2;int M[maxn],X[maxn]={},n,m;struct Land{ int i,j,v; Land(){} Land(int _i,int _j,int _v):i(_i),j(_j),v(_v){} bool operator<(const Land&o)const { if(i!=o.i)return i<o.i; return j<o.j; }}A[maxm];inline int Dist(int a,int b,int i,int j){ return (a-i)*(a-i)+(b-j)*(b-j);}int main(){ //freopen("in","r",stdin); scanf("%d%d",&n,&m);int x,y,v; rep(i,m)M[i]=-inf; rep(i,n) { scanf("%d%d%d",&x,&y,&v);–x;–y; A[i]=Land(x,y,v); } sort(A,A+n);int ret; M[0]=A[0].v; for(int i=1;i<n;i++) { x=A[i].i;y=A[i].j;v=A[i].v; ret=-inf; rep(j,y+1) ret>?=M[j]-Dist(x,y,X[j],j); ret+=v; M[y]=ret;X[y]=x; } printf("%dn",ret);}-44 101 1 2010 10 103 5 605 3 30

[Balkan2007]Dream

[Balkan2007]Dream

Time Limit:10000MS Memory Limit:165536K
Total Submit:3 Accepted:2
Case Time Limit:1000MS

Description

Input

N在[3,200]
M在[3,10000]
K在[2,200000]
L在[2,30000]

Output

Sample Input

Sample Output

Hint

5 2 1
2 1 2
3 7 4
Pic. 1

5 2 1
2 1 2
3 7 4
Pic. 2

5 2 1
2 1 2
3 7 4
Pic. 3

5 2 1
2 1 2
3 7 4
Pic. 4

5 2 1
2 1 2
3 7 4
Pic. 5

5 2 1
2 1 2
3 7 4
Pic. 6

5 2 1
2 1 2
3 7 4
Pic. 7

5 2 1
2 1 2
3 7 4
Pic. 8

5 2 1
2 1 2
3 7 4
Pic. 9

5 2 1
2 1 2
3 7 4
Pic. 10

5 2 1
2 1 2
3 7 4
Pic. 11

5 2 1
2 1 2
3 7 4
Pic. 12

Source

Code：

#include<cstdio>#include<algorithm>#include<iostream>#define rep(i,n) for(int i=0;i<n;i++)using namespace std;const int maxn=200,maxm=10000,maxk=200000,maxw=1000000,maxs=300;typedef long long ll;int mod,k,n,m,Div[maxw+1],L[maxs],dn=0,Next[maxs][maxs];inline void Add(int&x,int c){x+=c;x%=mod;}inline void Mult(int&x,int c){x*=c;x%=mod;}int Dp[2][maxs],c1[maxs],c2[maxs];int main(){ //freopen("in","r",stdin); scanf("%d%d%d%d",&n,&m,&k,&mod); for(int i=1;i<=k;i++)if(k%i==0)L[dn++]=i; rep(i,dn)rep(j,dn) for(int k=dn-1;k>=0;k–)if(ll(L[i])*L[j]%L[k]==0) { Next[i][j]=k;break; } rep(i,dn) { int x=L[i]; for(int j=x;j<=maxw;j+=x)Div[j]=i; } int x,now=0,old=1; rep(i,m)scanf("%d",&x),Add(Dp[now][Div[x]],1); rep(i,n-1) { swap(now,old);memset(Dp[now],0,sizeof Dp[now]); memset(c1,0,sizeof c1); memset(c2,0,sizeof c2); rep(i,m)scanf("%d",&x),Add(c1[Div[x]],1); memcpy(c2,c1,sizeof c1); if(i!=n-2) rep(a,dn)rep(b,a+1) if(a!=b)Add(c2[Next[a][b]],c1[a]*c1[b]*2); else Add(c2[Next[a][b]],c1[a]*(c1[a]-1)); rep(a,dn)rep(b,dn) Add(Dp[now][Next[a][b]],Dp[old][a]*c2[b]); } printf("%dn",Dp[now][dn-1]);}123 312 1005 2 12 1 23 7 4

[HNOI2008]神奇的国度

[HNOI2008]神奇的国度

Time Limit:20000MS Memory Limit:165536K
Total Submit:150 Accepted:41
Case Time Limit:5000MS

Description

K国是一个热衷三角形的国度,连人的交往也只喜欢三角原则.他们认为三角关系:即AB相互认识,BC相互认识,CA相互认识,是简洁高效的.为了巩固三角关系,K国禁止四边关系,五边关系等等的存在.所谓N边关系,是指N个人
A1A2…An之间仅存在N对认识关系:(A1A2)(A2A3)…(AnA1),而没有其它认识关系.比如四边关系指ABCD四个人
AB,BC,CD,DA相互认识,而AC,BD不认识.全民比赛时,为了防止做弊，规定任意一对相互认识的人不得在一队，国王相知道，最少可以分多少支队。

Input

Output

Sample Input

Sample Output

Hint

Source

AekdyCoin神牛的题解才明白这是个弦图。。所以有专门的算法。。

Code：
#include <vector>

#include <cstdio>
#include <iostream>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define tr(e,x) for(it e=x.begin();e!=x.end();e++)
const int maxn=10000+10;
using namespace std;
typedef vector<int>::iterator it;
int n,m,cnt[maxn]={},c[maxn]={},hash[maxn]={};
bool v[maxn]={};
vector<int> E[maxn],ord;
int main()
{
//freopen("in","r",stdin);
scanf("%d%d",&n,&m);int s,t;
while(m–)scanf("%d%d",&s,&t),–s,–t,E[s].pb(t),E[t].pb(s);
rep(i,n)
{
int max=-1,t;
rep(j,n)if(!v[j]&&cnt[j]>max)max=cnt[j],t=j;
v[t]=true;tr(e,E[t])cnt[*e]++;
ord.pb(t);
}
c[ord[0]]=1;
for(int id=1;id<=n-1;id++)
{
int t=ord[id];
tr(e,E[t])hash]=id;
rep(i,n)if(hash[i+1]!=id){c[t]=i+1;break;}
}
int ans=0;rep(i,n)ans>?=c[i];
printf("%dn",ans);
}

34 51 21 42 42 33 4

C++里面一点小技巧。。。

#define

1. #x

#define Debug(x) cout<<#x<<"="<<(x)<<endl;
int i=5;Debug(i);

2.##x

#define D(x) m##x
int D(x)=0;cout<<m1<<endl;

#define D(x) int m##x=0
D(0);D(1);D(2);D(3);D(4);D(5);D(6);D(7);
3.多行
#define是可以多行的。只要在除了最后一行的每一行后面加一个就可以了。。

#define Swap(T,x,y)
{
T tmp=x;x=y;y=tmp;
}
int a=0,b=1;Swap(int,a,b);Debug(a);Debug(b);

a<?b <=> min(a,b)
a>?b <=>max(a,b)
a<?=b <=> a=min(a,b)
a>?=b <=> a=max(a,b)

[Ceoi2006]Queue

[Ceoi2006]Queue

Time Limit:10000MS Memory Limit:65536K
Total Submit:17 Accepted:12
Case Time Limit:1000MS

Description

If you are an average football fan, you probably know that obtaining tickets for this year’s World Cup in Germany was an impossible task. Greedy organizers and football federations grabbed the majority or available tickets and divided them among sponsors, friends and family members. As a result, jet setters have flooded the venues, while die-hard fans sit at home enjoying the games between advertisements featuring crappy beer and sugar-free chewing gum.
A couple of tickets are left for the final game and a huge queue has formed in front of the ticker office. As fans were arriving, they were labeled with successive integers. The first person in queue was labeled with number one, the second with number two, etc.
Since the fans arrived the night before, they had to wait for a long time before the ticket counter was open and, naturally, some of them had to use the restroom. Each time a person needs to use the restroom, he/she steps out of the queue and, and, after completing the task, steps back into the queue, though not necessarily at the same position as before. Since there is only one restroom available no person leaves the queue before the previous person has returned (hence, at any moment there is at most one person missing from the queue).
During the course of the night, a total of N restroom visits have occurred. Each visit is described by two positive integers A and B, denoting that the person labeled A stepped out of the queue and the stepped back into the queue immediately in front of the person labeled B. Now that all the visits have completed, the officials have to answer a series of questions. Each question is either of the form ‘P X’, asking for the position lf the person labeled X, or of the form ‘L X’, asking for the label of the person at position X.
The first person in queue is considered to be at position one, the second at position two, etc.
Write a program that, given the description of the visits and a number of questions, answers all of the questions.

Input

The first line of input contains an integer N(2 ≤ N ≤ 50 000)- the total number of restroom visits.
Each of the following N lines contains two different integers A and B (1 ≤ A, B ≤ 109), describing one restroom visit. The nest line contains an integer Q (1 ≤ Q ≤ 50 000) – the total number of questions.
Each of the following Q lines contains a single character (either the uppercase letter ‘P’ or the uppercase letter ‘L’) and an integer X (1≤ X ≤109) , describing one question.

Output

The output should consist of a total of Q lines.
The ith line or output should contain a single integer R – the answer to the ith question.
If the corresponding question is of the form ‘P Xi’ then R should be the final position of the person labeled Xi.
If the corresponding question is of the form ‘L Xi’ then R should be the label of the person at position Xi.

Partial credit is awarded for incorrect solutions that correctly answer all questions of one type. If all questions of the form ‘P X’ are answered correctly or if all questions of the form ‘L X’ are answered correctly, you will receive 50% of the corresponding test case.
In order to receive partial credit, the output should be formatted according to the specifications. Therefore, even if you choose to answer only one type of questions, you should still produce output for all questions of the other type.

Sample Input

Sample Output

Source

Code：
#include <vector>

#include <algorithm>
#include <utility>
#include <cstdio>
#include <map>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define All(x) x.begin(),x.end()
const int inf=2e9,maxn=50000+10;
using namespace std;
map<int,int> Pre,Next;
int n,m,Ans[maxn];
int pre(int x){return Pre.count(x)?Pre[x]:x-1;}
int next(int x){return Next.count(x)?Next[x]:x+1;}
typedef pair<int,int> ii;
typedef vector<ii>::iterator it;
vector<ii> L,P;
void init()
{
scanf("%d",&n);int a,b;
rep(i,n)
{
scanf("%d%d",&a,&b);
Next[pre(a)]=next(a);
Pre[next(a)]=pre(a);
Next[pre(b)]=a;
Pre[a]=pre(b);
Next[a]=b;
Pre[b]=a;
}
Next[inf]=inf+1;
char c;scanf("%d",&m);
rep(i,m)
{
scanf(" %c %d",&c,&a);
if(c==’P’)P.pb(ii(a,i));
else L.pb(ii(a,i));
}
L.pb(ii(inf,m));P.pb(ii(inf,m));
sort(All(L));sort(All(P));
}
void Solve()
{
int now=0,Min,pos=0;
while(now<inf)
{
int a=Next.lower_bound(now)->first-now;
int b=lower_bound(All(L),ii(pos,0))->first-pos;
int c=lower_bound(All(P),ii(now,0))->first-now;
Min=a<?b<?c;
now+=Min;pos+=Min;
if(Min==b)
{
it l=lower_bound(All(L),ii(pos,0)),r=lower_bound(All(L),ii(pos+1,0));
for(it i=l;i!=r;i++)
Ans[i->second]=now;
}
if(Min==c)
{
it l=lower_bound(All(P),ii(now,0)),r=lower_bound(All(P),ii(now+1,0));
for(it i=l;i!=r;i++)
Ans[i->second]=pos;
}
now=next(now);
++pos;
}
rep(i,m)printf("%dn",Ans[i]);
}
int main()
{
init();Solve();
}

103154411000009999926 39 68L 1L 2L 3L 4P 1P 2P 3P 4Output12961256Input57 22 79 710 110005 99959L 1P 2L 2P 7L 7P 9P 10P 99999P 100000

[JSOI2008]最小生成树计数

[JSOI2008]最小生成树计数

Time Limit:1000MS Memory Limit:165536K
Total Submit:100 Accepted:38

Description

Input

Output

Sample Input

Sample Output

Source

。。算法的话很显然对于所有一组权值相同的边，它们以最大数量加入之后，造成的连通性是一样的，那么从小到大算出每一组边，乘起来就OK了。。

Code：
#include <vector>

#include <iostream>
#include <map>
#include <utility>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
const int mod=31011,maxn=100,maxm=1000;
using namespace std;
typedef pair<int,int> ii;
struct UF
{
int F[maxn];
void clear(){rep(i,maxn)F[i]=i;}
int find(int x)
{
if(F[x]==x)return x;
return F[x]=find(F[x]);
}
bool Union(int i,int j)
{
i=find(i);j=find(j);
return F[i]=j,i!=j;
}
UF& operator=(const UF&u)
{
memcpy(F,u.F,sizeof(F));
return *this;
}
};
int n,m,ans=1,get,ret;
typedef map<int,vector<ii> >::iterator mit;
map<int,vector<ii> > M;
vector<ii> now;
void Dfs(int p,int c)
{
if(p==now.size())
{
if(c==get)ret++;
return;
}
Dfs(p+1,c);
}
int main()
{
cin>>n>>m;int s,t,c;
rep(i,m)
{
cin>>s>>t>>c;s–;t–;
M.pb(ii(s,t));
}
All.clear();s=0;
for(mit i=M.begin();i!=M.end();i++)
{