@bzoj - [email protected] [POI2015] ?asuchy

目录

  • @[email protected]
  • @[email protected]
  • @accepted [email protected]
  • @[email protected]

@[email protected]

圆桌上摆放着 n 份食物,围成一圈,第 i 份食物所含热量为 c[i]。

相邻两份食物之间坐着一个人,共有 n 个人。每个人有两种选择,吃自己左边或者右边的食物。如果两个人选择了同一份食物,这两个人会平分这份食物,每人获得一半的热量。

假如某个人改变自己的选择后(其他 n-1 个人的选择不变),可以使自己获得比原先更多的热量,那么这个人会不满意。

请你给每个人指定应该吃哪一份食物,使得所有人都能够满意。

input

第一行一个整数 n (2<=n<=1000000),表示食物的数量(即人数)。食物和人都从1~n编号。

第二行包含 n 个整数 c[1], c[2], …, c[n](1<=c[i]<=10^9)。

假设第 i 个人(1<=i<n)左边是第 i 份食物,右边是第 i+1 份食物;而第 n 个人左边是第 n 份食物,右边是第 1 份食物。

output

如果不存在这样的方案,仅输出一行 NIE。

如果存在这样的方案,输出一行共 n 个整数,第 i 个整数表示第 i 个人选择的食物的编号。如果有多组这样的方案,输出任意一个即可。

sample input

5

5 3 7 2 9

sample output

2 3 3 5 1

@[email protected]

网上的题解(至少在我能看到的)大多采用的是如下的方法:

我们记 dp[i][s] 表示第 i 份食物被左右两个人选择的状态为 s 是否合法(0 <= s < 4)

拆环成链:在第 n 个人的右边,即第 n + 1 份食物处放上第 1 份食物。

枚举第一份食物被吃的状态,递推到第 n + 1 份,再 check 第 n + 1 份的状态是否等于第一份食物。

dp 的时候记录转移,就可以输出方案了。

然而。。。在我的不懈努力下,我乱搞出来了另外一个解法:

首先可以发现如果一个人某一边的食物 >= 另一边的两倍,则他选择这一边的食物一定不亏。

我们称这个人具有绝对占优策略。

这并不能说明什么。但是,考虑这样一个情况:所有人都不具有绝对占优策略。

这个时候,第 i 个人选择第 i 份食物总是一个合法的解。

证明可以采用反证法:如果第 i 个人改变选择而第 i + 1 个人不改变选择导致第 i 个人收益更大,则说明 c[i + 1] > c[i]*2。矛盾。

是否我们可以去掉具有绝对占优策略的人,再将剩下的人按上面的方法(第 i 个人选择第 i 份食物)进行处理?

对,也不完全对。

因为如果一个人的策略确定了,可能会导致其他人从不确定的状态转为确定的状态。

(举个例子:某个人旁边是 6 7,是不确定的。这个时候他旁边的人选择了 6,他变成了 3 7,就是确定的了)

需要在第一次去掉过后再继续寻找新的。

如果直接迭代 “寻找具有绝对占优策略的人”->“删除他们”,时间复杂度是 O(n^2) 的。

但是,我们发现一个人的策略只会影响他左右的人的策略。

所以可以将他左右的人加入队列(为了偷懒我用的栈),再进行进一步的处理。

这样就是 O(n) 的了。

同时这也表示不会存在无解的情况。

@accepted [email protected]

给出两份代码,分别对应上面的两类解法。

第一份:

#include<cstdio>
const int MAXN = 1000000 + 5;
inline int read() {
    int x = 0; char ch = getchar();
    while( ch > ‘9‘ || ch < ‘0‘ ) ch = getchar();
    while( ‘0‘ <= ch && ch <= ‘9‘ ) x = 10*x + ch-‘0‘, ch = getchar();
    return x;
}
inline void write(int x) {
    if( !x ) return ;
    write(x/10);
    putchar(x%10 + ‘0‘);
}
int c[MAXN], pre[4][MAXN], n;
bool dp[4][MAXN];
void print(int i, int j) {
    if( j == 0 ) return ;
    print(pre[i][j], j - 1);
    printf("%d ", (j + (i&1)) > n ? 1 : (j + (i&1)) );
}
bool check(int x) {
    for(int i=0;i<=n;i++)
        dp[0][i] = dp[1][i] = dp[2][i] = dp[3][i] = false;
    dp[x][0] = true;
    for(int i=1;i<=n;i++) {
        if( dp[2][i-1] && c[i]   <= c[i-1]   ) dp[0][i] = true, pre[0][i] = 2;
        if( dp[3][i-1] && 2*c[i] <= c[i-1]   ) dp[0][i] = true, pre[0][i] = 3;
        if( dp[0][i-1] && c[i]   >= c[i-1]   ) dp[1][i] = true, pre[1][i] = 0;
        if( dp[1][i-1] && 2*c[i] >= c[i-1]   ) dp[1][i] = true, pre[1][i] = 1;
        if( dp[2][i-1] && c[i]   <= 2*c[i-1] ) dp[2][i] = true, pre[2][i] = 2;
        if( dp[3][i-1] && 2*c[i] <= 2*c[i-1] ) dp[2][i] = true, pre[2][i] = 3;
        if( dp[0][i-1] && c[i]   >= 2*c[i-1] ) dp[3][i] = true, pre[3][i] = 0;
        if( dp[1][i-1] && 2*c[i] >= 2*c[i-1] ) dp[3][i] = true, pre[3][i] = 1;
    }
    if( dp[x][n] ) {
        print(x, n);
        return true;
    }
    return false;
}
int main() {
    n = read();
    for(int i=0;i<n;i++)
        c[i] = read();
    c[n] = c[0];
    for(int i=0;i<4;i++)
        if( check(i) ) return 0;
    puts("NIE");
}

第二份:

#include<cstdio>
const int MAXN = 1000000;
int ans[MAXN + 5], tag[MAXN + 5], n;
int c[MAXN + 5], stk[MAXN + 5], top = 0;
inline int nxt(int x) {return (x + 1 == n) ? 0 : x + 1;}
inline int pre(int x) {return (x == 0) ? n - 1 : x - 1;}
inline bool Check(int i, int j) {
    if( tag[i] == -1 ) {
        if( tag[j] == 1 ) return c[i]*2 > c[j];
        else return c[i] > c[j];
    }
    else {
        if( tag[j] == 1 ) return c[i] > c[j];
        else return c[i] > c[j]*2;
    }
}
inline int read() {
    int x = 0; char ch = getchar();
    while( ch > ‘9‘ || ch < ‘0‘ ) ch = getchar();
    while( ‘0‘ <= ch && ch <= ‘9‘ ) x = 10*x + ch-‘0‘, ch = getchar();
    return x;
}
void write(int x) {
    if( !x ) return ;
    write(x/10);
    putchar(x%10 + ‘0‘);
}
int main() {
    scanf("%d", &n);
    for(int i=0;i<n;i++) {
        c[i] = read();
        ans[i] = -1; tag[i] = 0;
    }
    for(int i=0;i<n;i++) {
        if( ans[i] != -1 ) continue;
        stk[++top] = i;
        while( top ) {
            int x = stk[top--];
            if( Check(x, nxt(x)) ) {
                ans[x] = x;
                if( ans[nxt(x)] == -1 ) stk[++top] = nxt(x), tag[nxt(x)] = -1;
                if( ans[pre(x)] == -1 ) stk[++top] = pre(x), tag[x] = 1;
            }
            else if( Check(nxt(x), x) ) {
                ans[x] = nxt(x);
                if( ans[nxt(x)] == -1 ) stk[++top] = nxt(x), tag[nxt(x)] = 1;
                if( ans[pre(x)] == -1 ) stk[++top] = pre(x), tag[x] = -1;
            }
        }
    }
    for(int i=0;i<n;i++)
        if( ans[i] == -1 ) ans[i] = i;
    for(int i=0;i<n;i++) write(ans[i] + 1), putchar(‘ ‘);
    puts("");
}

@[email protected]

一查,这道题居然还有什么专业背景,叫什么帕累托最优什么的……

不过这不重要。

dp 竟然卡我内存……不开 bool 还会 MLE……

如果我的乱搞做法有什么问题(因为我也没找到跟我一样做法的人所以不知道其正确性),请务必告诉我,谢谢。

原文地址:https://www.cnblogs.com/Tiw-Air-OAO/p/10362179.html

时间: 02-11

@bzoj - [email protected] [POI2015] ?asuchy的相关文章

$*和[email&#160;protected]之间区别代码分析

#!/bin/bash set 'apple pie' pears peaches for i in $*           /*单引号被去掉,循环单个字符输出*/ do echo $i done [[email protected] Ex_14.02-14.31]# sh 14-14-1 apple pie pears peaches -------------------------------------------------------------- #!/bin/bash set

[email&#160;protected]一个高效的配置管理工具--Ansible configure management--翻译(六)

无书面许可请勿转载 高级playbook Finding files with variables All modules can take variables as part of their arguments by dereferencing them with {{ and }} . You can use this to load a particular file based on a variable. For example, you might want to select a

【转载】 ERROR 1045 (28000): Access denied for user [email&#160;protected] (using password: NO)

来自:http://www.jb51.net/LINUXjishu/10981.html 错误描述: Mysql中添加用户之后可能出现登录时提示ERROR 1045 (28000): Access denied for user的错误.删除user.user中值为NULL的,或更新NULL为test 1)delete from user where user is NULL 2)update user set user='test' where user is NULL.意外的情况: 如果上述方

[[email&#160;protected]] Omit catch error block if not needed

From [email protected], you can omit catch error block. Before: try { throw new Error('whatever'); } catch(err) { console.log(err) } Now: try { throw new Error('whatever'); } catch { console.log("error happened") } It is just a syntax sugar, if

[email&#160;protected]动态代理-类加载器

一.测试单元     概述:用于测试JAVA代码的工具类,已内置在Eclipse中;     格式:         1.在方法的上面添加@Test;         2.对被测试的方法的要求:权限-public;返回值-void;参数-空参         [email protected]:在@Test标注的方法前执行,可以用于初始化;           @After:在@Test标注的方法后执行,可以用于释放资源; 二.注解     概述:java的一种数据类型,和类/接口在同一级别  

git push报错error: failed to push some refs to &#39;[email&#160;protected]:

$ git push -u origin master To [email protected]:xxx/xxx.git ! [rejected] master -> master (fetch first) error: failed to push some refs to '[email protected]:xxx/xxx.git' hint: Updates were rejected because the remote contains work that you do hint:

Https方式使用[email&#160;protected]设置密码的方式

62561_silentboy Zoker3 years ago member https方式每次都要输入密码,按照如下设置即可输入一次就不用再手输入密码的困扰而且又享受https带来的极速 设置记住密码(默认15分钟): git config --global credential.helper cache 如果想自己设置时间,可以这样做: git config credential.helper 'cache --timeout=3600' 这样就设置一个小时之后失效 长期存储密码: git

mysql Access denied for user [email&#160;protected]错误解决方法总结(转)

mysql Access denied for user [email protected]错误解决方法总结(转) mysql Access denied for user \'root\'@\'localhost\'”解决办法总结,下面我们对常见的出现的一些错误代码进行分析并给出解决办法,有需要的朋友可参考一下. 错误代码 1045 Access denied for user 'root'@'localhost' (using password:YES) 解决办法是重新设置root用户密码,

解决[email&#160;protected]&#39;s password:localhost:permission denied,please try again

背景:在装完Hadoop及jdk之后,在执行start-all.sh的时候出现 [email protected]'s password:localhost:permission denied,please try again 可是,我记得当时设置的密码是对的,无论怎么输都不对 解决方法:在出现上述问题后,输入 [cpp] view plain copy sudo passwd 然后,会输入新的密码,设置之后,再重新格式化一下namenode,最后执行start-all.sh,OK. 解决[em

CenOS7.1 [email&#160;protected]:1.service: control process exited, code=exited status=2

参考:http://www.cnblogs.com/gaohong/p/4829206.html 报错细节: [email protected]:1.service: control process exited, code=exited status=2 主要原因:因为异常关机导致临时文件生成错误 解决办法:删除vncserver产生的临时用户文件X1([email protected]:1.service对应的)