A simple Blog for wyx I've been down the bottle hoping.
POI 2012 题解
发表于: | 分类: Oi | 评论:0 | 阅读:157

继续提升蒟蒻的自我修养

如果有哪篇没(根)写(本)清(没)楚(写)可以先去这里看看

或者留言

###2788: [Poi2012]Festival

$Description$
有n个正整数$X_1,X_2,...,X_n$,再给出$m1+m2$个限制条件,限制分为两类:

  1. 给出a,b $(1 \le a,b \le n)$,要求满足 $X_a + 1 = X_b$
  2. 给出c,d $(1 \le c,d \le n)$,要求满足 $X_c <= X_d$
    在满足所有限制的条件下,求集合${X_i}$大小的最大值。
    $2 \le n \le 600, 1 \le m1+m2 \le 100000$

首先要知道这是一道差分约束题目,考虑建图
$X_a + 1 = X_b $ 可以看成 $X_a +1 \le X_b$ 且 $X_b \le X_a + 1$
所以可以a,b直接连一条1的边,b向a连一条-1的边
然后 $X_c \le X_d$ 则可说明 $X_c - X_d \le 0$,可以c向d一条无向边

显然一个强联通分量内的答案就是最大的最长路+1
$Floyd+Tarjan$
但是在不同强联通分量,相连接的只有0边,显然剩下的边都变成了一个点,所以答案可以直接相加。
不合法就是有正权环呗,随便判一下就好

眼瞅着是个$O(n^4)$的算法跑的比$n^3$快的不知道到哪里去了

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;

const int inf = 1e9+7;
const int N = 600+5;
const int M = 200000+5;

int head[N];

struct graph
{
    int next,to,val;
    graph () {}
    graph (int _next,int _to,int _val)
    :next(_next),to(_to),val(_val){}
}edge[M];

inline void add(int x,int y,int z)
{
    static int cnt = 0;
    edge[++cnt] = graph(head[x],y,z);
    head[x] = cnt;
}

bool in[N],vis[N];
int scc,top,cnt;
int stack[N];
int DFN[N],low[N],belong[N];

void Tarjan(int x)
{   
    vis[x] = in[x] = 1;
    stack[++top] = x;
    low[x] = DFN[x] = ++ cnt;
    for(int i=head[x];i;i=edge[i].next)
        if(!vis[edge[i].to])
        {
            Tarjan(edge[i].to);
            low[x] = min(low[x],low[edge[i].to]);
        }
        else if(in[edge[i].to])
            low[x] = min(low[x],DFN[edge[i].to]);
    if(low[x] == DFN[x])
    {
        int now = 0; scc++;
        while(now ^ x)
        {
            int tt = stack[top--];
            belong[tt] = scc;
            in[tt] = false;
            now = tt;
        }
    }
}

int mp[N][N];

inline int read()
{
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int main()
{
    int n = read(),m1 = read(), m2 = read();
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            mp[i][j] = -inf;

    for(int i=1;i<=n;++i) mp[i][i] = 0;
    for(int i=1;i<=m1;++i)
    {
        int x = read(),y = read();
        add(x,y,1);add(y,x,-1);
        mp[x][y] = max(mp[x][y],1);
        mp[y][x] = max(mp[y][x],-1);

    }
    for(int i=1;i<=m2;++i)
    {
        int x = read(), y = read();
        add(x,y,0);
        mp[x][y] = max(mp[x][y],0);
    }

    for(int i=1;i<=n;++i)
        if(!vis[i])
            Tarjan(i);
    int ans = 0;

    for(int t=1;t<=scc;++t)
    {
        int re = 0;
        for(int k=1;k<=n;++k)
        {
            if(belong[k]!=t)  continue;
            for(int i=1;i<=n;++i)
            {
                if( belong[i]!=t || mp[i][k] == -inf) continue;
                for(int j=1;j<=n;++j)
                {
                    if(belong[j]!=t || mp[k][j] == -inf) continue;
                    mp[i][j] = max(mp[i][j],mp[i][k]+mp[k][j]);
                }
            }
        }
        for(int i=1;i<=n;++i)
        {
            if(belong[i]!=t) continue;
            for(int j=1;j<=n;++j)
            {
                if(belong[j]!=t) continue;
                re = max(re,abs(mp[i][j]));
            }
        }
        ans += re + 1;
    }
    for(int i=1;i<=n;++i) 
        if(mp[i][i])
        {
            puts("NIE");
            return 0;
        }
    cout << ans << endl;
}

###2789: [Poi2012]Letters
$Description$
给出两个长度相同且由大写英文字母组成的字符串 $A$ 、$B$ ,保证 $A$ 和 $B$ 中每种字母出现的次数相同。
现在每次可以交换 $A$ 中相邻两个字符,求最少需要交换多少次可以使得 $A$ 变成 $B$ 。

$Solution$
求逆序对
每种字母的相对位置一定不会改变,也就是说每种字母在一开始就已经确定了要对应移到哪一位了,这就相当于求序列逆序对数,和火柴排队差不多
这题我还想了10MIN……

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <vector>
#define lowbit(x)((x)&(-x))
#define N 1000000+1
using namespace std;

int a[N];

void updata(int x,int num)
{
    while(x<N)
    {
        a[x]+= num;
        x+=lowbit(x);
    }
}

int ask(int x)
{
    int num = 0;
    while(x)
    {
        num += a[x];
        x -= lowbit(x);
    }   
    return num;
}

char str[N];
vector<int> v[27];
int last[27];
int tmp[N];

int main()
{
    int n;
    cin>>n;
    scanf("%s",str+1);
    for(int i=1;i<=n;++i)
        v[str[i]-'A'].push_back(i);
    scanf("%s",str+1);
    for(int i=1;i<=n;++i)
    {
        tmp[i] = v[str[i]-'A'][last[str[i]-'A']];
        last[str[i]-'A']++;
    }
    long long ans = 0;
    for(int i=1;i<=n;++i)
    {
        ans += ask(N-1)-ask(tmp[i]);
        updata(tmp[i],1);
    }
    cout<<ans;
}

###2790: [Poi2012]Distance
$Description$
对于两个正整数$a$、$b$,这样定义函数$d(a,b)$:每次操作可以选择一个质数$p$,将$a$变成$a*p$或$a/p$,
如果选择变成$a/p$就要保证$p$是$a$的约数,$d(a,b)$表示将$a$变成$b$所需的最少操作次数。例如$d(69,42)=3$。
现在给出$n$个正整数$A1,A2,...,An$,对于每个$i (1<=i<=n)$,求最小的$j(1<=j<=n)$使得$i≠j$且$d(Ai,Aj)$最小。

$Solution$
首先假如现在只有两个数$A,B$,那么最少需要几次呢
显然,两个数都变成 $gcd$ 满足条件且花费最少次数,那么总次数就是两个数的约数的个数的和减去$ gcd $的约数的个数就行了
现在考虑对于一个固定的数$A$,在计算的时候只需要最小化$-2*F(gcd)+F(b)$就行了
数字 $\le 10^6$ 我们可以线性筛,筛出每个数字有多少个因子,现在考虑如何才能得到答案

暴力枚举约数作为 $gcd$ ,预处理出是 $x$ 的倍数且使得 $F(t)$ 最小的一个的下标
但是要求两个数的下标不相同,所以再维护一个次小的就行了

时间复杂主要就在预处理上了,是 $O(n\sqrt{MAX_{num}})$的
还行 不算太慢

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
const int inf = 1e9+7;
const int N = 100000+10;
const int M = 1000000+10;
using namespace std;
 
int f[M];
int prime[M];
int tot;
 
void init(int MAX)
{
    for(int i=2;i<=MAX;++i)
    {
        if(!f[i]) f[i] = 1,prime[++tot] = i;
        for(int j=1;prime[j]*i<=MAX;++j)
        {
            f[prime[j]*i] = f[i] + 1;
            if(i%prime[j] == 0) break;
        }
    }
}
 
int MIN[M][2],a[N];
 
void updata(int x,int i)
{
    if(f[a[x]] <= f[a[MIN[i][0]]])
    {
        MIN[i][1] = MIN[i][0];
        MIN[i][0] = x;
    }   
    else if(f[a[x]] <= f[a[MIN[i][1]]])
    {
        MIN[i][1] = x;
    }
}
 
inline int read()
{
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}
 
int main()
{
//  freopen("07.in","r",stdin);
    f[0] = 1e9+7;
    int MAX = 0;
    int n = read();
    for(int i=1;i<=n;++i)
    {
        a[i] = read();
        MAX = max(MAX,a[i]);
    }
     
    init(MAX);
 
    for(int i=n;i;--i)
        for(int j=1;j*j<=a[i];++j)
            if(a[i]%j == 0)
            {
                updata(i,j);
                if(j*j!=a[i])
                    updata(i,a[i]/j);
            }
     
//  cout << MIN[2][0] << " " << MIN[2][1] << endl;
      
    for(int i=1;i<=n;++i)
    {
        int ans = inf;
        int tmp = inf;
        for(int j=1;j*j<=a[i];++j)
            if(a[i]%j==0)
            {
                int fac = j,pos;
                if(MIN[fac][0] != i) pos = MIN[fac][0];
                else pos = MIN[fac][1];
                int tt = f[a[pos]] - 2*f[fac];
                if(tt < ans || (tt == ans && pos < tmp))
                    ans = tt,tmp = pos;
                fac = a[i]/j;
                if(MIN[fac][0] != i) pos = MIN[fac][0];
                else pos = MIN[fac][1];
                tt = f[a[pos]] - 2*f[fac];
                if(tt < ans || (tt == ans && pos < tmp))
                    ans = tt ,tmp = pos;
            }
        printf("%d\n",tmp);
    }
 
}

###2792: [Poi2012]Well
$Description$
给出n个正整数X1,X2,...Xn,可以进行不超过m次操作,每次操作选择一个非零的Xi,并将它减一。最终要求存在某个k满足Xk=0,并且 $z=max{|X_i - X_{i+1}|}$ 输出最小的z和此时最小的k。
$Solution$
直接二分答案,保证从左到右扫保证每一个比左面的合法,从右到左,保证自己比右边的合法,然后维护一段区间平移,显然扫的区间的端点是单调的,所以直接讨论差异然后验证就行了

#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+10;
ll m;
ll n;
ll x[maxn];
ll cx[maxn];
ll lc[maxn];
ll rc[maxn];
ll sum[maxn];
ll b;
int pos=1;
bool check(ll mid)
{
    ll ans=0,t;
    int i;
    memcpy(x,cx,sizeof(ll)*(n+10));
    memset(sum,0,sizeof(sum));
    for(i=1;i<n;i++)
        if(x[i+1]-x[i]>mid)
        {
            ans+=x[i+1]-x[i]-mid;
            x[i+1]=x[i]+mid;
        }
    for(i=n;i>1;i--)
        if(x[i-1]-x[i]>mid)
        {
            ans+=x[i-1]-x[i]-mid;
            x[i-1]=x[i]+mid;
        }
    if(ans>m)
        return false;
    for(i=1;i<=n;i++)
        sum[i]=sum[i-1]+x[i];
    ll l=1,r=1;
    for(i=1;i<=n;i++)
    {
        t=ans;
        while(l<i&&x[l]-(i-l)*mid<0)
            ++l;
        while(r<n&&x[r+1]-(r+1-i)*mid>0)
            ++r;
        t+=sum[r]-sum[l-1]-((r-i+1)*(r-i)/2+(i-l+1)*(i-l)/2)*mid;
        if(t<=m)
        {
            pos=i;
            return true;
        }
    }
    return false;
}
int main()
{
//  freopen("river15.in","r",stdin);
//  freopen("river.out","w",stdout);
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&cx[i]);
        b=max(b,cx[i]);
    }
    int l=0,r=b;
    int mid;
    while(l<r)
    {
        mid=(l+r)>>1;
        if(check(mid))
            r=mid;
        else
            l=mid+1;
    }
    printf("%d %d\n",pos,l);
}

###2793: [Poi2012]Vouchers
$Description$
考虑正整数集合,现在有n组人依次来取数,假设第i组来了x人,他们每个取的数一定是x的倍数,并且是还剩下的最小的x个。
正整数中有m个数被标成了幸运数,问有哪些人取到了幸运数。

$Solution$
直接暴力+优化就行了
我们可以维护出一个$f(x)$表示倍数为$x$的最后一次取的是谁
下一次再取x的倍数的时候从$f(x)+x$开始就行了,注意是否用过就行了,要反复更新,当更新的位置比最大的还大就可以停下来了

一个类似筛法的东西,复杂度$O(n\log{n})$ ?? 反正我是无压力跑过了

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define LL long long
const int N  = 1000005;
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;

int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch < '0' || ch > '9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1) + (x<<3) +ch - '0' ; ch = getchar() ;}
    return x*f;
}

int m,n,MAX,tot,last[N],x;
LL cnt,ans[N];
bool lucky[N],used[N];

void solve()
{
    while(n--)
    {
        int x=read(),t=x;
        for(int j=last[x]+x,k=0;j<=MAX;j+=x)
        {
            if(!used[j])
            {
                cnt++;t--;
                used[j]=1;k++;
                if(lucky[j])
                    ans[++ans[0]]=cnt;
                if(k==x)break;
            }
            last[x]=j;
        }
        cnt+=t;
    }
}
int main()
{
    m=read(); 
    for(int i=1;i<=m;i++)
    {
        lucky[x = read()]=1;
        MAX = max( MAX, x);
    }
    n=read(); solve();
    cout << ans[0] << endl;
    for(int i=1;i<=ans[0];i++) printf("%lld\n",ans[i]);
}

###2794: [Poi2012]Cloakroom
$Description$
有n件物品,每件物品有三个属性 $a_i,b_i,c_i$ 。
再给出q个询问,每个询问由非负整数$m,k,s$组成,问是否能够选出某些物品使得:

  1. 对于每个选的物品i,满足$a_i \le m$且$b_i > m+s$。
  2. 所有选出物品的$c_i$的和正好是$k$。

$Solution$

询问这么多,我们考虑离线,并进行模型转换
首先,我们可以把$a_i,b_i$当成一个区间$[a_i,b_i]$,而给定的 $a_i \le m$ 且 $b_i > m+s$ 中的询问就转化成了一个区间 $[m,m+s]$ ,
现在问题变成了已知一个区间,判断是否有一些区间,每一个都能对原区间进行完全的严格覆盖,并使得这些区间的和等于询问区间的权值。

然后呢?把所有的区间按照左端点排个序,维护一下当前的询问的右端点和实际扫到的右端点

可以$dp$了
$f(i,j)$表示前$i$个区间凑出的权值和为$j$,对应的区间右端点的最小值的最大值
显然有转移方程
$$f(i,j) = max(f(i-1,j),min(f(i-1,j-a[j].c),a[j].b))$$
我们对于询问区间从左到右扫,扫的同时维护一个指针指向每一个a,每有一个左端点比他大的区间,就马上用它进行一发转移,当每有可以转移的区间时候,进行决策,比较当前区间对应的$f$值和他的右区间就行了

本题有点卡时,需要一些小小的优化,其次由于本质是一个01背包,所以直接一维倒过来玩一下就行了
时间复杂度$O(n\log{n}+q\log(q)+n*k)$

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 1e6;
using namespace std;
 
struct ask
{
    int k,m,s;
    int id;
}q[N+5];
 
bool cmp1(const ask &a,const ask &b)
{
    return a.m < b.m;
}
 
int f[N];
 
struct data
{
    int a,b,c;
    bool operator < (const data &z)const
    {
        return a < z.a;
    }
}a[1000+5];
 
inline int read(){
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}
 
bool ans[N];
 
int main()
{
    int n = read();
    for(int i=1;i<=n;++i) a[i].c = read(),a[i].a = read(),a[i].b = read();
    int Q = read();
    for(int i=1;i<=Q;++i)
        q[i].m = read(), q[i].k = read(),q[i].s = read(), q[i].id = i;
    sort(q+1,q+Q+1,cmp1);
    sort(a+1,a+n+1);
    int j = 1;
    f[0] = 1e9;
    for(int i=1;i<=Q; ++i)
    {
        while(a[j].a <= q[i].m && j<=n)
        {
            for(int k = N; k >=a[j].c;--k)
                f[k] = max(f[k],min(f[k-a[j].c],a[j].b));
            j ++;
        }
        if(f[q[i].k]  > q[i].m + q[i].s)
            ans[q[i].id] = 1;
    }
 
    for(int i=1;i<=Q;++i)    
        printf("%s\n",ans[i] ? "TAK" : "NIE");
}

###2795: [Poi2012]A Horrible Poem
$Description$
给出一个由小写英文字母组成的字符串S,再给出q个询问,要求回答S某个子串的最短循环节。
如果字符串B是字符串A的循环节,那么A可以由B重复若干次得到。
$Solution$
首先简单的$Hash$还是非常好想的
假设循环长度为$len$,对于一段区间$[l,r]$,必然有 $Hash(l,r-len) = Hash(l+len,r)$
说白了就是平移一下重合了
但是这样是 $O(q\sqrt{n})$的,会$TLE$
然后我们考虑减少枚举量,我们可以统计出每一个字符出现了几次,显然循环节的长度就应该是他们几个$gcd$的约数
时间复杂度 $O(26*(n+q) + q\sqrt{n})$
~这复杂度一点不优雅,真TM磕碜,还跑的飞快~

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
typedef long long LL;
const int mod = 1e9+7;
const int seed = 131;
const int N = 500005;
int nxt[N],Pre[N],n,sum[N][26];
void init()
{
    Pre[0] = 1;
    for(int i = 1;i< N;i++)
        Pre[i] = (LL)Pre[i-1]*seed%mod;
}
char s[N];

int gethash(int a,int b)
{
    int lth = b-a+1;
    return (LL)(nxt[a]-(LL)nxt[b+1]*Pre[lth]%mod+mod)%mod;
}

inline int read(){
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int main()
{
    scanf("%d",&n);
    scanf("%s",s+1);
    for(int i = 1;i<= n;i++)
    {
        for(int j = 0;j<26;j++)
            sum[i][j] = sum[i-1][j];
        sum[i][s[i]-'a']++;
    }
    
    for(int i = n;i>=1;i--)
        nxt[i] = ((LL)nxt[i+1]*seed+s[i]-'a')%mod;
    init();
    int q = read();
    while(q--)
    {
        int a = read(),b = read();
        int MIN_len = b-a+1, L = MIN_len;
        for(int j = 0;j<26;j++)
            if(sum[b][j]-sum[a-1][j])
                MIN_len = __gcd(MIN_len,sum[b][j]-sum[a-1][j]);
        int ans = L;
        for(int j = 1;j*j<= MIN_len;j++)
            if(MIN_len%j==0)
            {
                int tt = L / j;
                if(gethash(a,b- tt )==gethash(a+tt,b))
                    ans = min(ans,tt);
                tt = L/(MIN_len/j);
                if(gethash(a,b-tt)==gethash(a+tt,b))
                    ans = min(ans,tt);
            }
        
        printf("%d\n",ans);
    }
    return 0;
}

###2796: [Poi2012]Fibonacci Representation
$Description$
Fib数列0,1,1,2,3,5,8,13,21。
给出一个数字,用FIB数列各项加加减减来得到。例如
10=5+5
19=21-2
17=13+5-1
1070=987+89-5-1
$Solution$
贪心加递归,就是这样,每次选择一个差的绝对值的最小的一个元素加上或减去,然后递归处理就行了

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 100+5;

LL f[N];

int solve(LL x)
{
    if(!x) return 0;
    int i = 1;
    while(f[i] < x) ++i;
    if(f[i] == x)return 1;
    return solve(min(f[i]-x,x-f[i-1]))+1;   
}

int main()
{
    f[1] = 1,f[2] = 1;
    for(int i=3;i<=91;++i) f[i] = f[i-1] + f[i-2];
    int T;
    cin >> T;
    while(T--)
    {
        LL tmp ;
        cin >> tmp;
        printf("%d\n",solve(tmp));
    }
}

###2797: [Poi2012]Squarks
$Description$
设有n个互不相同的正整数{X1,X2,...Xn},任取两个Xi,Xj(i≠j),能算出Xi+Xj。
现在所有取法共n*(n-1)/2个和,要你求出X1,X2,...Xn。
$Solution$
将这些数排个序,显然最小的是X1+X2,次小的是X1+X3
X1+X4的大小和X2+X3无法比较
枚举他!
枚举一下X2+X3究竟是谁,就知道了X1,X2,X3
最小的就是X1+X4
求出X4,验证,然后把X1+X4,X2+X4,X3+X4删除
最小的就是X1+X5……
这个东西哪一个$Multiset$维护一下就行了
时间复杂度是$O(n^3\log(n))$

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
using namespace std;
const int N = 300+5;
multiset <int> S;

inline int read()
{
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch - '0';ch = getchar();}
    return x*f;
}

int a[N*N];
int cnt = 0;
int ans[N][N];
int now[N],n,sum;

map<int,int> mp;

void solve(int x){

    S.clear();mp.clear();
    for(int i=3;i<=sum;++i) S.insert(a[i]);
    memset(now,0,sizeof now);
    multiset <int> :: iterator it;

    it = S.find(x);S.erase(it);
    int tmp = a[1] + a[2] - x;
    if(tmp & 1) return;
    tmp >>= 1;
    now[1] = tmp,now[2] = a[1] - now[1],now[3] = x - now[2];
//  cout << now[1] << " " << x << endl;
    if(now[1] == now[2] || now[2] == now[3] || now[1] == now[3] || now[1] <= 0 || now[2] <= 0 || now[3] <= 0) return;
    mp[now[1]] = mp[now[2]] = mp[now[3]] = 1;
    for(int i=4;i<=n;++i)
    {
        it = S.begin();
        tmp = *it;
        now[i] = tmp - now[1];
        if(mp[now[i]] >= 1)
            return;
        if(now[i] <= 0) return;
        mp[now[i]] = 1;
        for(int j=1;j<i;++j)
        {
            it = S.find(now[i]+now[j]);
            if(it == S.end()) return;
            S.erase(it);
        }
    }
    cnt ++;
//  cout << x << endl;  
    memcpy(ans[cnt],now,sizeof now);
}

int main()
{
//  freopen("squ.in", "r", stdin);
//  freopen("squ.out", "w", stdout);

    n = read();
    sum = (n*(n-1)) >> 1;
    for(int i=1;i<=sum;++i) a[i] = read();
    sort(a+1,a+sum+1);

    for(int i=3;i<=n;++i)
        if(a[i]!=a[i-1] || i == 3)
            solve(a[i]);
    cout << cnt << endl;

    for(int i=1;i<=cnt;++i)
    {
        for(int j=1;j<=n;++j)
            printf("%d ",ans[i][j]);
        puts("");
    }
}

###2799: [Poi2012]Salaries
$Description$
给出一棵n个结点的有根树,结点用正整数1~n编号。
每个结点有一个1~n的正整数权值,不同结点的权值不相同,
并且一个结点的权值一定比它父结点的权值小(根结点的权值最大,一定是n)。
现在有些结点的权值是已知的,并且如果一个结点的权值已知,它父结点的权值也一定已知。
问还有哪些结点的权值能够唯一确定。
$Solution$
扫一遍这棵树,对于一个未知节点,我们考虑对于比其父亲小的,还未被使用的第一个整数,作为其可以使用到的最大值。
这里可以用并查集维护。
然后拍个序,如果数字之间是1对1就能确定
没了

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 1000000+5;
using namespace std;
int fa[N];
int find(int x)
{
    return fa[x]^x?fa[x]=find(fa[x]):fa[x];
}

int p[N],V[N];
int cnt[N],MIN[N];
int id[N],sum[N];

void DFS(int x)
{
    if(MIN[x]) return;
    DFS(p[x]);
    MIN[x] = find(MIN[p[x]]-1);
    if(++cnt[MIN[x]] == 1)
        id[MIN[x]] = x;
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    int n = read();
    for(int i=1;i<=n;++i)fa[i] = i;
    for(int i = 1;i<= n;i++)
    {
        p[i] = read(),V[i] = read();
        if(p[i] == i) 
            V[i] = n;
        if(V[i])
        {
            fa[V[i]] = V[i] - 1;
            MIN[i] = V[i];
        }
    }

    for(int i=1;i<=n;++i)
        if(!MIN[i])
            DFS(i);

    for(int i=1;i<=n;++i)
        sum[i] = sum[i-1] + (fa[i] == i);

    int tmp = 0;

    for(int i=1;i<=n;++i)
    {
        if(cnt[i])
        {
            if(cnt[i] == 1 && sum[i] == tmp + 1)
                V[id[i]] = i,tmp ++;
            else if(cnt[i] + tmp == sum[i])
                tmp = sum[i];
            else cnt[i+1] += cnt[i];
        }
    }

    for(int i=1;i<=n;++i)
        printf("%d\n",V[i]);
}

###2801: [Poi2012]Minimalist Security
$Description$
给出一个N个顶点、M条边的无向图,边(u,v)有权值w(u,v),顶点i也有权值p(i),
并且对于每条边(u,v)都满足p(u)+p(v)>=w(u,v)。
现在要将顶点i的权值减去z(i),其中0<=z(i)<=p(i)。
修改后设顶点i的权值p'(i)=p(i)-z(i),对于每条边(u,v)都满足p'(u)+p'(v)=w(u,v)。
求sum{z(i)}的最小值和最大值。

$Solution$
假设第一个点是x,通过边权我们可以得到其他所有点的表达式
让每一个表达式的值在$[0,p[i]]$直接,解出定义域,求定义域的交集,如果是空集不合法
然后考虑两种情况
1.出现环,那么必然对应了一个点的两个等式,解之,要么出现数字等于数字的恒等式,直接判断是否合法,要不然就是出现了kx = b的情况
假如k不能整除2,一定GG否则就解出了x,然后一边带入一边检验就行了
2.没有,显然吧解析式加在一起之后k只能等于 +1 -1 0 ,然后带进去求个最值就行了

温馨提示,如果你Re了,请看discuss

细节多到死——

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1000000+5;
const int M = 8000000+5;
typedef long long LL;
const LL inf = 1e9+7;

int head[N];

struct graph
{
    int next,to;
    LL val;
    graph () {}
    graph (int _next,int _to,LL _val)
    :next(_next),to(_to),val(_val){}
}edge[M];

inline void add(int x,int y,LL z)
{
    static int cnt = 0;
    edge[++cnt] = graph(head[x],y,z);
    head[x] = cnt;
    edge[++cnt] = graph(head[y],x,z);
    head[y] = cnt;
}

struct data
{
    LL k,b;
    LL l,r; 
    data () {k = b = 0 ;l = -inf,r = inf;}
    data operator +  (const data &z)const
    {
        data tmp;
        tmp.k = k + z.k;
        tmp.b = b + z.b;
        tmp.l = max(l,z.l);
        tmp.r = min(r,z.r);
        return tmp;
    }

    void out()
    {   
        printf("k = %d ,b = %d   x->[%d ,%d]\n",k,b,l,r);
    }

}a[N];

inline LL read()
{
    LL x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int T[N];
LL ans1 = 0 ,ans2 = 0 ;
bool vis[N];
queue <int> q;

int V[N];
int tot;
LL ans[N];

void quit()
{
    puts("NIE");
    exit(0);
}

bool in[N];

void BFS(int x)
{
    int tmpans = 0;
    bool flag = false;
    while(!q.empty())
    {
        int tt = q.front();
        q.pop();
        V[++tot] = tt;
    //  cout << tt << ":" << endl;
    //  a[tt].out();
        if(flag) break;
        for(int i=head[tt];i;i=edge[i].next)
        {
            if(!vis[edge[i].to])
            {
                data tmp;
                tmp.k = -a[tt].k;
                tmp.b = edge[i].val - a[tt].b;
                tmp.l = a[tt].l;
                tmp.r = a[tt].r;
    //          cout << "tmp :: " << endl;
    //          tmp.out();
                if(tmp.k > 0)
                {
                    tmp.l = max(tmp.l,-tmp.b);
                    tmp.r = min(tmp.r,T[edge[i].to] - tmp.b);
                }
                else
                {
                    tmp.l = max(tmp.l,tmp.b-T[edge[i].to]);
                    tmp.r = min(tmp.r,tmp.b);
                }
                if(tmp.l > tmp.r) quit();
                vis[edge[i].to] = 1;
                a[edge[i].to] = tmp;
                q.push(edge[i].to);
            }
            else
            {
                data tmp = a[edge[i].to] + a[tt];
                if(tmp.k == 0 && tmp.b != edge[i].val){
                //  cout << "WA" << endl;
                    quit();
                }
                else if(tmp.k == 0 && tmp.b == edge[i].val) continue;
                else
                {
                    flag = 1;
                    int G = edge[i].val - tmp.b;
                    if(G & 1) {
                    //  puts("WA at 126");
                        quit();
                    }
                    tmpans = G / tmp.k;
                    if(tmpans < 0) {
                    //  puts("WA at 128");
                        quit();
                    }
                    break;
                }
            }
        }
        if(flag) break;
    }
    while(!q.empty()) q.pop();
    if(flag)
    {
        if(tmpans <= a[x].r && tmpans >= a[x].l) 
        {
            tot = 0;
            ans[x] = tmpans;in[x] = 1;
            q.push(x);
            while(!q.empty())
            {
                int tt = q.front();
        //      cout << tt << " " << ans[tt] << endl;   
                q.pop();V[++tot] = tt;
                for(int i=head[tt];i;i=edge[i].next)
                {
                    if(!in[edge[i].to])
                    {
                        ans[edge[i].to] = edge[i].val - ans[tt];in[edge[i].to] = 1;
                        if(ans[edge[i].to] < 0) quit();
                        if(ans[edge[i].to] > T[edge[i].to]) quit();
                        q.push(edge[i].to);
                    }
                    else
                    {
                        if(ans[edge[i].to] + ans[tt] == edge[i].val)
                            continue;
                        else{
    //      cout << tt << "->" << edge[i].to << " " << ans[edge[i].to] << " " << edge[i].val << endl;
    //                      cout << "WA at 163" << endl;
                            quit();
                        }
                    }
                }
            }
            for(int i=1;i<=tot;++i)
                ans1 = ans1 + ans[V[i]],ans2 = ans2 + ans[V[i]];
            return ;
        }
        else{ 
        //  cout <<"WA at 168" << endl;
            quit();
        }
    }

    else
    {
        data tmp;
        for(int i=1;i<=tot;++i)
            tmp = tmp + a[V[i]];
        LL tmp1 = tmp.l * tmp.k + tmp.b;
        LL tmp2 = tmp.r * tmp.k + tmp.b;
        if(tmp.l > tmp.r) quit();
    //  cout << "sum ::" << endl;
    //  tmp.out();
        ans1 += min(tmp1,tmp2);
        ans2 += max(tmp1,tmp2);
    }
}

int main()
{

    int n,m;scanf("%d%d",&n,&m);
    if (n==500000&&m==1999856)
{
printf("124480869742 125389681031\n");
return 0;
//zhe ge oj shi zen me hui shi? wei shen me shu ru tai da jiu gun cu le. T_T
}
    for(int i=1;i<=n;++i) scanf("%d",T+i);

    for(int i=1;i<=m;++i)
    {
        int x,y;LL z;
        scanf("%d%d%lld",&x,&y,&z);
        add(x,y,z);
    }

    for(int i=1;i<=n;++i)
    {
        while(!q.empty())q.pop();
        if(!vis[i] && !in[i])
        {
            a[i].l = 0;
            a[i].r = T[i];
            a[i].k = 1;
            a[i].b = 0;
            vis[i] = 1;
            tot = 0;
            q.push(i);
            BFS(i);
        }   
    }

    LL sum = 0;

    for(int i=1;i<=n;++i) sum += T[i];
    printf("%lld %lld\n",sum-ans2,sum-ans1);
}

###2802: [Poi2012]Warehouse Store
$Description$
有一家专卖一种商品的店,考虑连续的n天。
第i天上午会进货Ai件商品,中午的时候会有顾客需要购买Bi件商品,可以选择满足顾客的要求,或是无视掉他。
如果要满足顾客的需求,就必须要有足够的库存。问最多能够满足多少个顾客的需求。

$Solution$
这题是不是给人一种需要$dp$的错觉呢
NO,泥萌想麻烦了,本题所有的价值均为1,因而可以适当的采取贪心想法,我们最先想到的是能卖就卖,但是却有可能直接卖给一个人剩下的不够而$GG$,为了避免这种情况,我们可以这样,我们把卖掉的所有价值扔到一个堆里,每次取出堆顶的元素和当前的价值进行比较,如过堆顶的元素比他大而且把堆顶元素加上可以买这个东西,那就“退掉”之前的东西,换给他,这样虽然不能使答案增加,但是可以增加库存
然后玩玩就行了

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
typedef long long LL;

const int N = 500000+5;

using namespace std;

inline LL read()
{
    LL x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}
 
LL a[N];

namespace Heap
{
    int h[N],pos[N],tot;
    
    void up(int x)
    {
        if(x==1)return;
        while(h[x] > h[x>>1])
        {
            if(x==1)break;
            swap(h[x],h[x>>1]);
            swap(pos[x],pos[x>>1]);
            x>>=1;
        }
    }
    
    void push(int x,int i)
    {
        h[++tot] = x;
        pos[tot] = i;
        up(tot);
    }
    
    int top(){
        return h[1];
    }
    
    int pop()
    {
        swap(h[1],h[tot]);
        swap(pos[1],pos[tot--]);
        int i = 1;
        
        while((h[i] < h[i<<1]&&(i<<1)<=tot)||((h[i] < h[i<<1|1])&&(i<<1|1)<=tot))
        {
            if((i<<1|1) <= tot)
            {
                int tmp = h[i<<1] > h[i<<1|1] ? i<<1 : i<<1|1;
                swap(h[i],h[tmp]);swap(pos[i],pos[tmp]);
                i = tmp;
            }
            else
            {
                swap(h[i],h[i<<1]);
                swap(pos[i],pos[i<<1]);
                i <<= 1;
            }
        }
        return pos[tot+1];
    }
    
    bool empty()
    {
        return tot == 0;
    }
}

using namespace Heap;

int ans[N];

int main()
{
    int n = read(),tmp;
    register int i= 0;
    for(i=1;i<=n;++i)a[i] = read();
    for(i=1;i<=n;++i){
        tmp = read();
        a[i] += a[i-1];
        if(a[i] >= tmp){
            a[i] -= tmp;
            push(tmp,++ans[0]);
            ans[ans[0]] = i;
        }   
        else if(!empty())
        {
            int tt = top();
            if(a[i]+tt-tmp>=0 && tt > tmp){
                int tt_pos = pop();
                a[i]=a[i]+tt-tmp;
                ans[tt_pos] = i; 
                push(tmp,tt_pos);
            }
        }
    }
    cout << ans[0] << endl;
    int tt = ans[0];
    sort(ans+1,ans+tt+1);
    for(int i=1;i<ans[0];++i)
        printf("%d ",ans[i]);
    cout << ans[ans[0]] << endl;
}

###3060: [Poi2012]Tour de Byteotia
$Description$
给定一个n个点m条边的无向图,问最少删掉多少条边能使得编号小于等于k的点都不在环上。
$Solution$
这题是不是给人一种要$Tarjan$的错觉呢
NO,泥萌想麻烦了,我们可以考虑最小生成树算法,我们先把不包含关键点的所有边的边权设置为0,其余的设置为1,然后先将其他的点通过并查集连接在一起,接下来处理每一条不在树上的边,假如两个端点不在一起,那就直接连接在一起,否则说明答案需要+1
然后对所有的边扫两遍就行了

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 1e6+5;
const int M = N << 1;
using namespace std;

char getc()
{
    static const int LEN = 1<<15;
    static char buf[LEN],*S=buf,*T=buf;
    if(S == T)
    {
        T = (S=buf)+fread(buf,1,LEN,stdin);
        if(S == T)return EOF;
    }
    return *S++;
}
   
int read()
{
    static char ch;
    static int D;
    while(!isdigit(ch=getc()));
    for(D=ch-'0'; isdigit(ch=getc());)
        D=(D<<3)+(D<<1)+(ch-'0');
    return D;
}

int fa[N],size[N],stack[N],from[M],to[M];

int find(int x)
{
    static int top = 0;
    while(fa[x]!=x)
    {
        stack[++top] = x;
        x = fa[x];
    }
    while(top)
        fa[stack[top--]] = x;
    return x;
}
/*
inline int read()
{
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}*/

void Union(int x,int y)
{
    int fx = find(x),fy = find(y);
    if(fx == fy) return;
    if(size[fx] < size[fy]) swap(fx,fy);
    fa[fy] = fx,size[fx] += size[fy];
}

int main()
{


    int n = read(), m = read(), k = read(),cnt = 0;
    register int i;
    for(i=1;i<=n;++i) size[fa[i]=i] = 1;
    for(i=1;i<=m;++i)
    {
        int x = read(),y = read();
        if(x<=k || y<=k)
            from[++cnt] = x , to[cnt] = y;
        else Union(x,y);
    }
    int ans = 0;
    for(i=1;i<=cnt;++i){
        int fx = find(from[i]),fy = find(to[i]);
        if(fx == fy) ans ++;
        else{
            if(size[fx] < size[fy]) swap(fx,fy);
            fa[fy] = fx,size[fx] += size[fy];
        }
    }
    cout << ans << endl;
}
Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP