[Shoi2007]Setstack 集合堆栈机

[Shoi2007]Setstack 集合堆栈机

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

Description

中学数学里集合的元素往往是具体的数字,比如A = {1,2,3},B = {}(空集)等等。但是要特别注意,集合的元素也可以是另一个集合,比如说C = {{}},即说明C有且仅有一个元素——空集B,所以称B是C的子集或者称B是C的元素都是正确的。所谓一个集合的势,就是这个集合的元素个数,一般记为|S|,空集的势为0。在上例中,|A| = 3,|B| = 0,|C| = 1。
鉴于集合论是现代数学的基础理论这一事实,一群异想天开的科学家开始着手建造一台新式的超级计算机——集合堆栈机Alpha,这台机器操作的将是集合而不是数字。不过由于Alpha的竣工之日遥遥无期,科学家们希望你为他们编写一台虚拟机,好让他们检查自己的原型设计是否合理。
Alpha的存储设备只有一个栈,栈的每个单元都只能放置一个集合。一开始,栈是空的,在每个操作结束后,计算机就会输出位于栈顶单元的那个集合的势。Alpha拥有五种不同的指令,分别为:PUSH、DUP、UNION、INTERSECT和ADD,他们的功能如下:

Input

第一行只有一个整数n(0≤n≤2000),代表将要执行的指令条数。接下来有n行,每行有包含一条大写的指令,我们保证每条指令都是上述五条指令中的一条,并且虚拟机总是能正确执行完所有的指令。

Output

输出虚拟机的输出结果即可。每行输出一个大于或等于0的整数,代表虚拟机执行该条指令后的输出。选手们务必仔细考量程序的执行效率。

Sample Input

Sample Output

Hint

对于20%的数据,n ≤ 10。
对于100%的数据,n ≤ 2000。

Source
额。。这道题目只要给每个集合设计一个Hash函数就好办了。。我看oimaster大神说的是
全部xor一个值然后乘起来。。然后我自己也想了一个。。就是把所有的子集的Hash值排序一下
然后直接效仿Rabin—Karp..关键是如果这么搞全是0.。。所以再加个修正值。。。神奇的1A囧。。
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

9PUSHDUPADDPUSHADDDUPADDDUPUNION

[CQOI2007]余数之和sum

[CQOI2007]余数之和sum

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

Description

给出正整数n和k,计算j(n, k)=k mod 1 + k mod 2 + k mod 3 + … + k mod n的值,其中k mod i表示k除以i的余数。
例如j(5, 3)=3 mod 1 + 3 mod 2 + 3 mod 3 + 3 mod 4 + 3 mod 5=0+1+0+3+3=7

Input

输入仅一行,包含两个整数n, k。

Output

输出仅一行,即j(n, k)。

Sample Input

Sample Output

Hint

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

Source
额。。k mod i=k-(k/i)*i。。。
那么对于一段k/i相等的可以一起计算。。
可以证明最多分成sqrt(n)段。。
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

囧啊。。看上去很难的题目。。首先肯定是要DP的。但是暴力Dp是N^2额囧。。
显然要优化。。怎么优化呢?Dp的复杂度=状态数*每个状态计算需要的时间。。。
状态数肯定变变不了,是N个。。考虑减少后一项,
也就是当前需要考虑的过去状态个数,注意到加入A可以到达B,B可以到达C的话,
显然不会用A来更新C。。。从上到下,从左到右考虑,那么每列最多一个是有用的。。
就可以弄出一个NM的算法了。。。
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

给出N行M列的数字矩阵.
从第一行的数列中选一个数字,从最后一行的数列中选一个数字.
从其它的行中,每行取一到两个数.
将取出来的数字相乘,希望其可以被K整除.
你只需要输出结果Mod L的值.

Input

第一行给出N,M
第二行给出K,L
下面有N行M列,用于描述数字矩阵
其值在[1,1000000]各不相同.

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

Output

取法总数Mod L

Sample Input

Sample Output

Hint

以下为样例的12种取法.
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
好吧这题不算难。。但是挺有意思的。。一开始我想的是记录对K的每种余数有多少个,但那样显然太SB了。。。。后来我感觉这样很浪费啊。。实际上当前唯一有用的信息是与K的最大公约数!!。。。而K的约数不会超过300个(还记得反素数那个题目么。。特意算了下)。。所以毫无压力的就可以A掉了。。。需要与处理一下两个约数相乘之后与K的最大公约数。。。。以及每个数与K的最大公约数(类似筛法的搞)。。。
另外最近一直在看TopCoder SRM Level 3的题目。。有了不少感触啊。。有时间写个表格饿囧。。
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

第一行两个整数N,M。1<=N<=10000,1<=M<=1000000.表示有N个人,M对认识关系.
接下来M行每行输入一对朋友

Output

输出一个整数,最少可以分多少队

Sample Input

Sample Output

Hint

一种方案(1,3)(2)(4)

Source
哎。。总算差不多做完HNOI2008了。。我真是个傻叉啊。。
这题当时就把我震惊了。。一点思路都没有。。最小染色数不是NP问题么?
后来看了
AekdyCoin神牛的题解才明白这是个弦图。。所以有专门的算法。。
神牛已经说的很清楚了。。Orz!!!!!!!
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

SRM 472

悲剧了。。第一题是水题。。写了个暴力DP找规律。。
然后脑子抽筋了跳过第二题去做第三题。算法想出来了。。。但是脑残一直搞错了些东西。。最后没时间写些special case的检查了。。悲剧啊。。。
卧槽。。我这个水平也太烂了。。。4个月白过了囧。。。

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

额。。神牛别骂我火星额囧。。只是最近看到一些C++中比较神奇的东西。。。
#define
其实define的作用大得惊人。。可以大大简化代码甚至代替template
1. #x
先看下这个代码
#define Debug(x) cout<<#x<<"="<<(x)<<endl;
int i=5;Debug(i);
可能你不知道#x是什么意思,不过运行一下啊就会发现结果是i=5说明#x就是带进去的这个东西的字符串形式。。运用这个形式,可以方便的做一个像上面那个那个Debug的函数,像我这样从来不调试的NC来说,真是福音啊。。
2.##x
一样,先看下这个代码
#define D(x) m##x
int D(x)=0;cout<<m1<<endl;
结果能输出并且就是0.。
也就是说##x就是把它看成原来的一段字符(不是字符串)接在后面。。
运用这个可以很方便的声明和初始化多个变量。。。
#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);
这样就可以甚至拿来代替template。。这种东西在某些大量使用的代码段中可以大大方便Coder
还有一些很强大的符号
a<?b <=> min(a,b)
a>?b <=>max(a,b)
a<?=b <=> a=min(a,b)
a>?=b <=> a=max(a,b)
另外我快被Java搞死了。。这玩意太精细了。。写起来累死人。。。晚上就要有TopCoder比赛了。。我还是用C++算了。。.
最诡异的是algorithm这个库居然能够加快程序的速度?????见鬼啊。。

[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.

一开始将一列人按编号从1开始顺序排列,然后进行N次操作,每次将编号为A的人拿出,放在编号为B的人前面,所有操作进行完后有Q个问题,询问编号为X的人的位置,或者询问在X号位置上的人的编号。

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.

Grading
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
额。。。这题实际上只要注意到一种技术叫实时离散化,由于范围很大而n很小,很多块都是连续的。。那么信息可以忽略,只需要记录一些转角地方的点前驱和后继就可以了。。然后一遍扫描过去就可以得出所有的答案了。。我的程序鬼速到了极点。。囧啊。。
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

现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树,而希望知道这个图中有多少个不同的最小生成树。(如果两颗最小生成树中至少有一条边不同,则这两个最小生成树就是不同的)。由于不同的最小生成树可能很多,所以你只需要输出方案数对31011的模就可以了。

Input

第一行包含两个数,n和m,其中1<=n<=100; 1<=m<=1000; 表示该无向图的节点数和边数。每个节点用1~n的整数编号。
接下来的m行,每行包含两个整数:a, b, c,表示节点a, b之间的边的权值为c,其中1<=c<=1,000,000,000。数据保证不会出现自回边和重边。
注意:具有相同权值的边不会超过10条。

Output

输出不同的最小生成树有多少个。你只需要输出数量对31011的模就可以了。

Sample Input

Sample Output

Source
这题是老题了。。本来想A掉爽一下的,结果WA半天,最后发现还可能有无生成树的情况囧。。。
。。算法的话很显然对于所有一组权值相同的边,它们以最大数量加入之后,造成的连通性是一样的,那么从小到大算出每一组边,乘起来就OK了。。
如果数据大一点的话只好用矩阵来算答案了。。不过这里范围这么小暴力就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;
UF All,Link;
vector<ii> now;
void Dfs(int p,int c)
{
    if(p==now.size())
    {
        if(c==get)ret++;
        return;
    }
    ii t=now[p];UF tmp=Link;
    if(Link.Union(t.first,t.second))Dfs(p+1,c+1);
    Link=tmp;
    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++)
    {
        now=i->second;Link=All;get=0;ret=0;
        rep(j,now.size())get+=All.Union(now[j].first,now[j].second);
        Dfs(0,0);ans*=ret;ans%=mod;s+=get;
    }
    if(s<n-1)cout<<0<<endl;
    else cout<<ans<<endl;
}

84 61 2 11 3 11 4 12 3 22 4 13 4 1

Page 2 of 3123