1. 领土划分

【问题描述】

著名的女王,阳姐•查兰•伊丽莎白一世有两个宠物,一个叫大黄,一个叫小
昊。女王赐予了这两个宠物一份 N×M 的土地。这片土地由 N×M 个长度为一单
位的小正方形构成,每一个小正方形种植水稻或者小麦,但种植的量可能不同。
大黄喜欢吃饭,也就是说,他希望他的领地里的水稻种植量多,类似的,小
昊喜欢吃面,所以他希望他的领地里的小麦种植量多。为了这片土地的划分,大
黄与小昊经常发生狗咬狗、相煎何太急的惨剧。
现在女王决定,派出一辆推土机,这辆推土机从左上角开始,每次向右向下
或者向右下移动一个格子,直到走到土地的右下角为止,推土机经过的格子将变
为废墟。这样就会将土地分成上下两块,其中右上的那一块归小昊,左下的那一
块归大黄。
现在女王想知道,这辆推土机如何移动,能够使得大黄领地中水稻种植总量
和小昊领地中小麦种植总量之和最大?

【输入】

输入文件名为 Divide.in。
输入第一行包含两个正整数 N 和 M,表示土地的行数与列数。
下接一个 N×M 的矩阵描述这块土地的信息,其中,每个格子的信息按照如
下方式表示:若该格子种的是水稻,则形式为“JX”,其中 X 为该格子中水稻的
种植量;若该格子种的是小麦,则形式为“KX”,其中 X 为该格子中小麦的种
植量。保证种植量均为小于等于 99 的非负整数,且每一行中相邻两个格子之间

有逗号隔开。

【输出】

输出文件名为 Divide.out。
输出第一行包含一个正整数,为可能的最大的两种作物种植量总和。

【输入输出样例】

Divide.in
4 3
K2 K3 K5
J3 K1 J1
J2 J4 K1
K1 K3 J3

Divide.out
17

【样例解释】

移动方法为向右下,向右下,向下。总和为(3+2+4)+(3+5)=17。【数据范围】
40%的数据保证 1<=N,M<=100。
100%的数据保证 1<=N,M<=1500。数据保证有梯度。

题解

DP+前缀和优化
设$f_{i,j}$为以(i,j)为起点时的答案

$f_{i,j}=max\{f_{i+1,j+1}+sum1+sum2,f_{i+1,j}+sum1,f_{i,j+1}+sum2\}$

sum1表示坐标(i,j)所在的那一行中在(i,j)右边的小麦种植总量,sum2表示坐标(i,j)所在的那一列中在(i,j)下面的水稻种植总量

sum1、sum2用前缀和就可以了

代码:

#include <bits/stdc++.h>
#define NS (1505)
using namespace std;
template<typename _Tp>inline void SPR(_Tp&dig)
{
    char c=getchar();bool f=0;dig=0;
    while(!isupper(c))c=getchar();
    if(c=='K')f=1;
    c=getchar();
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
    if(f)dig=-dig;
}
int n,m,mp[NS][NS],sumj[NS][NS],sumk[NS][NS],f[NS][NS];
int main()
{
    freopen("divide.in","r",stdin),freopen("divide.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)SPR(mp[i][j]);
    for(int i=n;i>=1;i--)
        for(int j=m;j>=1;j--)
            if(mp[i][j]>0)sumk[i][j]=sumk[i][j+1],sumj[i][j]=sumj[i+1][j]+mp[i][j];
            else sumk[i][j]=sumk[i][j+1]-mp[i][j],sumj[i][j]=sumj[i+1][j];
    for(int i=n;i>=1;i--)
        for(int j=m;j>=1;j--)
        {
            if(i<n&&j<m)f[i][j]=max(f[i][j],f[i+1][j+1]+sumj[i+1][j]+sumk[i][j+1]);
            if(i<n)f[i][j]=max(f[i][j],f[i+1][j]+sumk[i][j+1]);
            if(j<m)f[i][j]=max(f[i][j],f[i][j+1]+sumj[i+1][j]);
        }
    printf("%d\n",f[1][1]);
    return 0;
}

2. 扑克游戏

【题目描述】

著名的阳姐•查兰•伊丽莎白一世因为治理国家太有方了,最近国泰民安,阳
姐就只能和大黄或者小昊开始玩扑克游戏了。
这个扑克游戏的规则是这样的。首先,弄出 N(N 保证为偶数)张牌(当我
没说扑克吧),每张牌上都有一个分数 Wi,抽到这张牌的人将得到 Wi 的分数。
将这 N 张牌按照顺序叠成一叠。两个人轮流抽牌,每次都只能抽现存的最上面
的牌或者最下面的牌,并且不放回。当牌堆被抽光的时候,分数最高的人胜利。
因为女士优先,每次都是阳姐先抽。阳姐现在想知道,自己能不能赢,最多能得
到多少分,自己得到最高分的时候会抽到原牌堆中的哪些牌。(当两种抽法得到
的分数相等时,优先取最上面那张牌)这样说可能会有些不敬,不过由于阳姐出
色的(调)教(揉)练,小昊和大黄的智商可以视为极高,也就是说,双方都会
执行对自己最有利的抽法。

【输入】

输入文件名为 Poker.ni。
输入第一行一个正整数 N,代表牌堆中牌的个数。
第二行顺次包含 N 个数,代表牌堆中最上面的牌一直到最下面的牌的分数。

【输出】

输出文件名为 Joker.ans。
输出第一行为“WIN”或“LOSE”,代表赢或者输。
输出第二行代表阳姐最高的得分。
输出第三行 N/2 个正整数,代表阳姐得到最高得分的时候,按她抽到的先后
顺序,输出她抽到的牌在原来牌堆中的序号。

【输入输出样例】

Poker.in
10

Poker.out
8 4 1 6 3 1 9 7 6 6 WIN
28
1 10 8 6 4

【数据范围】

对于 60%的数据,1<=N<=100。
对于 100%的数据,1<=N<=1000,1<=Wi<=1000。

题解

。。。区间dp裸题
设$f1_{i,j}$为当前牌堆最上面的牌是第i张,最下面的牌是第j张时先手的最优解值,相应的f2表示后手的

当j-i为奇数,是后手抽牌,否则为先手抽牌

所以(伪代码):

if(后手走)
{
    if(抽牌堆顶端的牌更好)
        后手抽走顶端的牌,先手再从剩下的牌中抽
    else
        后手抽走最后一张牌,先手再从剩下的牌中抽
}
else
{
    if(抽牌堆顶端的牌更好)
        先手抽走顶端的牌,后手再从剩下的牌中抽
    else
        先手抽走最后一张牌,后手再从剩下的牌中抽
}

至于输出路径,记录状态转移的前驱就行了

代码:

#include <bits/stdc++.h>
#define NS (1005)
using namespace std;
int n,w[NS],f1[NS][NS],f2[NS][NS],bk[NS][NS];
void dfs(int l,int r)
{
    if(l>r)return;
    if(bk[l][r])
    {
        if(!((r-l+1)&1))printf("%d ",r);
        dfs(l,r-1);
    }
    else
    {
        if(!((r-l+1)&1))printf("%d ",l);
        dfs(l+1,r);
    }
}
int main()
{
    freopen("poker.in","r",stdin),freopen("poker.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&w[i]);
    for(int l=1;l<=n;l++)
        for(int i=1;i+l-1<=n;i++)
        {
            int j=i+l-1;
            if(l&1)
                if(f2[i+1][j]+w[i]>=f2[i][j-1]+w[j])
                    f2[i][j]=f2[i+1][j]+w[i],f1[i][j]=f1[i+1][j],bk[i][j]=0;
                else
                    f2[i][j]=f2[i][j-1]+w[j],f1[i][j]=f1[i][j-1],bk[i][j]=1;
            else
                if(f1[i+1][j]+w[i]>=f1[i][j-1]+w[j])
                    f1[i][j]=f1[i+1][j]+w[i],f2[i][j]=f2[i+1][j],bk[i][j]=0;
                else
                    f1[i][j]=f1[i][j-1]+w[j],f2[i][j]=f2[i][j-1],bk[i][j]=1;
        }
    if(f1[1][n]>=f2[1][n])printf("WIN\n");else printf("LOSE\n");
    printf("%d\n",f1[1][n]),dfs(1,n);
    return 0;
}

3. 罪人审判

【问题描述】

小昊是著名女帝,阳姐•查兰•伊丽莎白一世,的专属,宠物。
但是小昊人模人样,尤其是公正心,更是超乎正常人一等。所以阳姐委任他
担当最高法院最高大法官审判长一职。今天,大法官小昊审判了 N 个罪人,每
个人的罪恶度为 Di。按照惯例,这些罪人应该要背着跟他罪恶度相等重量的荆
棘游街示众。但是因为小昊的正义过头,导致这几天荆棘几乎卖完了,今天只有
M 个单位重量的荆棘了。万一某个罪人少背了 X 个单位的荆棘,那么民众对这
个罪人受到的处罚会产生 X 2 的不满值。现在小昊想知道,如何分配仅有的荆棘,
才能使民众对这 N 个犯人产生的不满值总和最小?对了,因为小昊的手无法抓
稳秤杆,所以每个罪人只能背整数单位的荆棘。

【输入】

输入第一行包含两个正整数 M 和 N,意义如上所述。
下接 N 行,每行一个正整数,为每个罪人的罪恶度 Di。

【输出】

输出一行包含一个正整数,代表最小的不满值总和。

【输入输出样例】

Output.txt(样例输入)
5 3
1
3
2

Input.txt(样例输出)
1

【数据范围】

40%的数据,M<=200000。
100%的数据,M,Di<=2.1*10 9 ,N<=10 5 ,保证答案大小在有符号 64 位整型变量
存储范围内。

题解

。。。被爆int只有40分了。。。
显然贪心
因为最后所有罪犯少背的重量是固定的,而且:
$a+b=c$时,$a^2+b^2<c^2$(因为$c^2=(a+b)^2=a^2+b^2+2ab$)
所以说白了就是要分配得最平均
O(n)的方法想了半天没想到,最后用平衡树(map)O(nlogn)搞的
思路是每次从平衡树中找出最大的(少背的最多的),再找出次大的,给最大的背上荆棘,让最大的少背的量和次大的相等,然后合并最大的和次大的节点,一直到用完荆棘或者全部为0(不满意度为0)
每个节点保存的是一种少背的量,可能有多个人对应了这个量,所以要保存这个量对应了多少人。

代码:

#include <bits/stdc++.h>
#define NS (100005)
using namespace std;
typedef long long LL;
LL n,m,ans=0;
map<LL,LL,greater<LL> > t;
int main()
{
    freopen("judge.in","r",stdin),freopen("judge.out","w",stdout);
    scanf("%lld%lld",&m,&n),t[0]++;
    for(LL i=1,a;i<=n;i++)scanf("%lld",&a),t[a]++;  
    while(m>0&&t.size()>1)
    {
        LL a=t.begin()->first,b=t.begin()->second;
        t.erase(t.begin());
        LL c=t.begin()->first;
        if((a-c)*b<m)m-=(a-c)*b,t[c]+=b;
        else a-=m/b,m%=b,t[a-1]+=m,t[a]+=b-m,m=0;
    }
    for(map<LL,LL>::iterator i=t.begin();i!=t.end();i++)
        ans+=i->first*i->first*i->second;
    printf("%lld\n",ans);
    return 0;
}

4. INDEX1

【问题描述】

INDEX 是谁?兄弟,这个问题你如果不知道我就只能怀疑你是从火星来的了。
但是,如果你真的不知道他是谁,那么,你可能和他拥有同一个故乡。
其实当年 INDEX 在火星上有 N 个基友和 M 个妹子,生活真是非常逍遥。他每天都把
基友和妹子排成一队,使得他能够站在最前面,领着他的基友后宫团游街(囧)。
但是,他的妹子们的嫉妒心是很强的,如果两个妹子站在一起,肯定会为 INDEX 吵得
不可开交。同时,INDEX 也是有老婆的人,他身后,也就是队伍的第一个人必须是他的基
友后宫团的团长——他老婆(也就是说,M 个妹子中有一个是他的老婆,为了使题目容易
理解,也就是第一个人已经确定是 M 个妹子中的一个了)。而且,他希望由一个基友来殿后。
现在 INDEX 想知道,他能够排成多少种不同的队伍,使得这个队伍满足他的要求?

【输入】

输入文件名为 Indexone.in。
输入一行包含两个整数 N 和 M。

【输出】

输出文件名为 Indexone.out。
输出一行,表示合法的队伍总数对 1000000007 的模值,如果不存在何方方案则输出 0。

【输入输出样例】

Indexone.in
1 1
Indexone.out
1

【数据范围】

对于 30%的数据,保证有 1≤N,M≤1000。
对于另外 30%的数据,保证有 1≤M≤10。
对于 100%的数据,保证有 1≤N,M≤1000000。

题解

组合数学。。。
第一个”老婆“是确定的一个人!没有M种选老婆的可能性!
可以把题目看成:n个男的组成n-1个盒子,再把m-1个女的丢到这n-1个盒子里

组成盒子的方案数是n!种,把m-1个女的丢进去的方案数时(n-1)×(n-2)×(n-3)×…×(n-m-1)
当然如果盒子数少于人数,答案为0

所以答案为:$n!×(n-1)×(n-2)×(n-3)×…×(n-m-1)$

代码:

#include <bits/stdc++.h>
#define MOD (1000000007)
using namespace std;
long long n,m,ans=1;
int main()
{
    freopen("indexone.in","r",stdin),freopen("indexone.out","w",stdout);
    scanf("%lld%lld",&n,&m),m--;
    if(m>n)printf("0\n"),exit(0);
    if(m==n)printf("1\n"),exit(0);
    for(int i=1;i<=n;i++)ans=(ans*i)%MOD;
    for(int i=1;i<=m;i++)ans=(ans*(n-i))%MOD;
    printf("%lld\n",ans);
    return 0;
}

4. INDEX2

【问题描述】

故事承接上文。
这事发生在博士还不那么内涵,现哥还不那么傻逼,姜嗲还没开始玩 dota,巨胖才 50Kg
的时候。有一天, INDEX 的老婆再也不能忍受 INDEX 那过分庞大超过一阿伏伽德罗常数的
后宫量,那天夜里,她将 INDEX 绑架到了飞船上,
“私奔”到了月球,在《Fly me to the moon》
的歌声中。好美啊!
这个时刻,INDEX 发现有一颗蓝色的星球一直在绕着一颗红色的星球转动。接着,他
又发现,他的故乡火星也一直在绕着这颗红色的星球转动!!!厉害爆了有木有!!!现在,他
的老婆将这颗蓝色星球命名为 A,他们的故乡火星命名为 B,并将他们的轨道平均分成 L
块,形成了 L 块扇形区域吗,并从 0 到 L-1 逆时针标号,A 星球和 B 星球都是沿逆时针绕
红色星球转动。一开始的时间计算为 0,在 0 时刻时,A 处在 Sa 块,B 处在 Sb 块。A 的移
动速度为 Va 块每 INDEX 小时,B 的移动速度为 Vb 块每 INDEX 小时。INDEX 向她老婆发
誓,
他们会在月球上度过一段美好的二人时光,
直到到某个 INDEX 小时整点的钟声敲响时,
若星球 A 和星球 B 所在块的编号相同,那么,他们启程返回火星。
思念自己庞大后宫团的 INDEX 想问你,他们启程返回火星的时刻。

【输入】

输入文件名为 Indextwo.in。
输入仅一行,包含五个正整数,分别为 L,Sa,Sb,Va,Vb。

【输出】

输出文件名为 Indextwo.out
输出仅一行,表示他们启程返回火星的时刻。若永远都不存在那个时刻,请输出
“Ohahahahahahaha”
,不包含双引号。

【输入输出样例】

Indextwo.in
3 1 1 2 2

Indextwo.out
0

【数据范围】

对于 30%的数据,保证有 1≤L≤100。
对于 100%的数据,保证有 1≤L≤1000000,而且 0≤Sa,Sb≤L-1,1≤Va,Vb≤L。

题解

首先令A的速度快于B的速度(如果B的速度较快就交换AB的速度与位置)
然后设v为va-vb(即速度差),d为(sb-sa+l) mod l(即A距离B多远)(l代表一圈的路程),然后巧设参考系,设B不动
那么大概是这个情况:

因为A第一次到达B的时候不一定是整数时间,所以可能A要再绕几圈,才能刚好在整点到达B。我们设还要绕x圈。
那么当前A的移动速度为v,初始距离为d,总路程为d+x×l,而且总路程一定能被v整除,即:
$(d+x\times l) mod v=0$
拆开:
$[d mod v+(x mod v)\times (l mod v)] mod v=0$
这里面d、v、l是定值,然后显然x小于v(因为如果x大于等于v取模后又小于v了,没有讨论的意义)。
那么我们从0到v-1枚举x的值,当$(d+x\times l) mod v=0$时就得到要转几圈了!
然后根据总路程可以算出总事件
显然如果不存在一个x能满足$(d+x\times l) mod v=0$,就无解了

代码:

#include <bits/stdc++.h>
using namespace std;
long long l,sa,sb,va,vb,d,v,ans=-1;
int main()
{
    freopen("indextwo.in","r",stdin),freopen("indextwo.out","w",stdout);
    scanf("%lld%lld%lld%lld%lld",&l,&sa,&sb,&va,&vb);
    if(va<vb)swap(va,vb),swap(sa,sb);
    d=(sb-sa+l)%l,v=va-vb;
    if(d==0)printf("0\n"),exit(0);
    for(long long i=0;i<v;i++)if((d+i*l)%v==0){ans=i;break;}
    if(ans==-1)printf("Ohahahahahahaha\n"),exit(0);
    printf("%lld\n",(d+ans*l)/v);
    return 0;
}

附:能用扩展欧几里德算法在log的复杂度内求出答案

分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *