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 的复杂度内求出答案
0 条评论