有些题目可能没做，如计算几何、恶心模拟。
| 高级打字机 |
| 难度级别：C； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
试题描述 |
早苗入手了最新的高级打字机。最新款自然有着与以往不同的功能，那就是它具备撤销功能，厉害吧。 请为这种高级打字机设计一个程序，支持如下3种操作： 1.T x：在文章末尾打下一个小写字母x。(type操作) 2.U x：撤销最后的x次修改操作。（Undo操作） （注意Query操作并不算修改操作） 3.Q x：询问当前文章中第x个字母并输出。（Query操作） 文章一开始可以视为空串。 |
输入 |
第1行：一个整数n，表示操作数量。 以下n行，每行一个命令。保证输入的命令合法。 |
输出 |
每行输出一个字母，表示Query操作的答案。 |
输入示例 |
7 T a T b T c Q 2 U 2 T c Q 2 |
输出示例 |
b c |
其他说明 |
对于20%的数据 n<=200; 对于50%的数据 n<=100000；保证Undo操作不会撤销Undo操作。 <高级挑战> 对于100%的数据 n<=100000；Undo操作可以撤销Undo操作。 <IOI挑战> 必须使用在线算法完成该题。 |
用可持久化线段树来维护数组就可以了
#include<cstdio>
#include<cctype>
#include<queue>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i!=-1;i=next[i])
using namespace std;
inline int read() {
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
const int maxnode=;
char S[maxnode];
int ToT,root[maxn],len[maxn],ls[maxnode],rs[maxnode];
void update(int& y,int x,int l,int r,int pos,char c) {
y=++ToT;
if(l==r) S[y]=c;
else {
int mid=l+r>>;ls[y]=ls[x];rs[y]=rs[x];
if(pos<=mid) update(ls[y],ls[x],l,mid,pos,c);
else update(rs[y],rs[x],mid+,r,pos,c);
}
}
void query(int y,int l,int r,int pos) {
if(l==r) printf("%c\n",S[y]);
else {
int mid=l+r>>;
if(pos<=mid) query(ls[y],l,mid,pos);
else query(rs[y],mid+,r,pos);
}
}
int main() {
int n=read(),vs=;
while(n--) {
char cmd[],s[];
scanf("%s",cmd);
if(cmd[]=='T') {
scanf("%s",s);vs++;len[vs]=len[vs-]+;
update(root[vs],root[vs-],,,len[vs],s[]);
}
else if(cmd[]=='U') {
int x=read();vs++;
root[vs]=root[vs-x-];
len[vs]=len[vs-x-];
}
else query(root[vs],,,read());
}
return ;
}
| 不等数列 |
| 难度级别：C； 运行时间限制：1000ms； 运行空间限制：256000KB； 代码长度限制：2000000B |
试题描述 |
将1到n任意排列，然后在排列的每两个数之间根据他们的大小关系插入“>”和“<”。问在所有排列中，有多少个排列恰好有k个“<”。答案对2012取模。 |
输入 |
第一行2个整数n,k。 |
输出 |
一个整数表示答案。 |
输入示例 |
5 2 |
输出示例 |
66 |
其他说明 |
对于30%的数据：n <= 10 对于100%的数据：k < n <= 1000， |
设f[n][k]表示1到n的排列，有k个<号的方案。
考虑将n+1插入n+1个位置中，如果插入到<之间不会增加<的数量，如果插入到>之间增加1个<。
#include<cstdio>
#include<cctype>
#include<queue>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i!=-1;i=next[i])
using namespace std;
inline int read() {
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int mod=;
const int maxn=;
long long f[maxn][maxn];
int main() {
int n=read(),k=read();
f[][]=;
rep(i,,n-) rep(j,,i-) {
f[i][j]%=mod;
f[i+][j]+=(j+)*f[i][j];
f[i+][j+]+=(i-j)*f[i][j];
}
printf("%lld\n",f[n][k]%mod);
return ;
}
| 经营与开发 |
| 难度级别：C； 运行时间限制：1000ms； 运行空间限制：256000KB； 代码长度限制：2000000B |
试题描述 |
4X概念体系，是指在PC战略游戏中一种相当普及和成熟的系统概念，得名自4个同样以“EX”为开头的英语单词。 eXplore（探索） eXpand（拓张与发展） eXploit（经营与开发） eXterminate（征服） ——维基百科 今次我们着重考虑exploit部分，并将其模型简化： 你驾驶着一台带有钻头（初始能力值w）的飞船，按既定路线依次飞过n个星球。 星球笼统的分为2类：资源型和维修型。（p为钻头当前能力值） 1.资源型：含矿物质量a[i]，若选择开采，则得到a[i]*p的金钱，之后钻头损耗k%，即p=p*(1-0.01k) 2.维修型：维护费用b[i]，若选择维修，则支付b[i]*p的金钱，之后钻头修复c%，即p=p*(1+0.01c) 注：维修后钻头的能力值可以超过初始值（你可以认为是翻修+升级） 请作为舰长的你仔细抉择以最大化收入。 |
输入 |
第一行4个整数n,k,c,w。 以下n行，每行2个整数type,x。 type为1则代表其为资源型星球，x为其矿物质含量a[i]； type为2则代表其为维修型星球，x为其维护费用b[i]； |
输出 |
一个实数（保留2位小数），表示最大的收入。 |
输入示例 |
5 50 50 10 1 10 1 20 2 10 2 20 1 30 |
输出示例 |
375.00 |
其他说明 |
对于30%的数据 n<=100 另有20%的数据 n<=1000；k=100 对于100%的数据 n<=100000; 0<=k,c,w,a[i],b[i]<=100；保证答案不超过10^9 |
设f[i]表示后i个星球最多获益值且必须采集第i个星球，DP维护一个最大值即可。
#include<cstdio>
#include<cctype>
#include<queue>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i!=-1;i=next[i])
using namespace std;
inline int read() {
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
int n,k,c,w,t[maxn],A[maxn];
double f[maxn],C,K,mx;
int main() {
n=read();k=read();c=read();w=read();
rep(i,,n) t[i]=read(),A[i]=read();
C=(+c)/100.0;K=(-k)/100.0;
dwn(i,n,) {
if(t[i]==) f[i]=mx*K+w*A[i];
else f[i]=mx*C-w*A[i];
mx=max(mx,f[i]);
}
printf("%.2lf\n",mx);
return ;
}
| 机器人 |
| 难度级别：C； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
试题描述 |
早苗入手了最新的Gundam模型。最新款自然有着与以往不同的功能，那就是它能够自动行走，厉害吧。 早苗的新模型可以按照输入的命令进行移动，命令包括‘E’、‘S’、‘W’、‘N’四种，分别对应东南西北。执行某个命令时，它会向对应方向移动一个单位。作为新型机器人，它可以执行命令串。对于输入的命令串，每一秒它会按命令行动一次。执行完命令串的最后一个命令后，会自动从头开始循环。在0时刻时机器人位于（0,0）。求T秒后机器人所在位置坐标。 |
输入 |
第1行：一个字符串，表示早苗输入的命令串，保证至少有1个命令 第2行：一个正整数T |
输出 |
2个整数，表示T秒时，机器人的坐标。 |
输入示例 |
NSWWNSNEEWN 12 |
输出示例 |
-1 3 |
其他说明 |
【数据范围】 对于60%的数据 T<=500,000 且命令串长度<=5,000 对于100%的数据 T<=2,000,000,000 且命令串长度<=5,000 【注意】 |
这个就不说了233
#include<cstdio>
#include<cctype>
#include<queue>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i!=-1;i=next[i])
using namespace std;
inline int read() {
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
char s[maxn];
int main() {
scanf("%s",s);int n=strlen(s);
int T=read();
int x0=,y0=;
rep(i,,n-) {
if(s[i]=='W') x0--;
if(s[i]=='E') x0++;
if(s[i]=='N') y0++;
if(s[i]=='S') y0--;
}
int x=x0*(T/n),y=y0*(T/n);
rep(i,,(T%n)-) {
if(s[i]=='W') x--;
if(s[i]=='E') x++;
if(s[i]=='N') y++;
if(s[i]=='S') y--;
}
printf("%d %d\n",x,y);
return ;
}
| 数列 |
| 难度级别：C； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
试题描述 |
a[1]=a[2]=a[3]=1 a[x]=a[x-3]+a[x-1] (x>3) 求a数列的第n项对1000000007（10^9+7）取余的值。 |
输入 |
第一行一个整数T，表示询问个数。 以下T行，每行一个正整数n。 |
输出 |
每行输出一个非负整数表示答案。 |
输入示例 |
3 6 8 10 |
输出示例 |
4 9 19 |
其他说明 |
对于30%的数据 n<=100； 对于60%的数据 n<=2*10^7； 对于100%的数据 T<=100，n<=2*10^9； |
直接矩阵快速幂即可
#include<cstdio>
#include<cctype>
#include<queue>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i!=-1;i=next[i])
using namespace std;
inline int read() {
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int MOD=;
typedef long long ll;
struct Matrix {
ll A[][];
Matrix() {memset(A,,sizeof(A));}
Matrix operator * (const Matrix& b) const {
Matrix c;
rep(i,,) rep(j,,) {
c.A[i][j]=;
rep(k,,) c.A[i][j]+=A[i][k]*b.A[k][j];
c.A[i][j]%=MOD;
}
return c;
}
void print() {
rep(i,,) {
rep(j,,) printf("%lld ",A[i][j]);
puts("");
}
}
};
void pow(Matrix& ans,int n) {
Matrix t=ans;n--;
while(n) {
if(n&) ans=ans*t;
t=t*t;n>>=;
}
}
ll solve(int n) {
if(n<=) return ;
Matrix t;
t.A[][]=;t.A[][]=;
t.A[][]=;t.A[][]=;
pow(t,n-);
return (t.A[][]+t.A[][]+t.A[][])%MOD;
}
int main() {
int T=read();
while(T--) printf("%lld\n",solve(read()));
return ;
}
| 虫洞 |
| 难度级别：C； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
试题描述 |
N个虫洞，M条单向跃迁路径。从一个虫洞沿跃迁路径到另一个虫洞需要消耗一定量的燃料和1单位时间。虫洞有白洞和黑洞之分。设一条跃迁路径两端的虫洞质量差为delta。 1.从白洞跃迁到黑洞，消耗的燃料值减少delta，若该条路径消耗的燃料值变为负数的话，取为0。 2.从黑洞跃迁到白洞，消耗的燃料值增加delta。 3.路径两端均为黑洞或白洞，消耗的燃料值不变化。 作为压轴题，自然不会是如此简单的最短路问题，所以每过1单位时间黑洞变为白洞，白洞变为黑洞。在飞行过程中，可以选择在一个虫洞停留1个单位时间，如果当前为白洞，则不消耗燃料，否则消耗s[i]的燃料。现在请你求出从虫洞1到N最少的燃料消耗，保证一定存在1到N的路线。 |
输入 |
第1行：2个正整数N,M 第2行：N个整数，第i个为0表示虫洞i开始时为白洞，1表示黑洞。 第3行：N个整数，第i个数表示虫洞i的质量w[i]。 第4行：N个整数，第i个数表示在虫洞i停留消耗的燃料s[i]。 第5..M+4行：每行3个整数，u,v,k，表示在没有影响的情况下，从虫洞u到虫洞v需要消耗燃料k。 |
输出 |
一个整数，表示最少的燃料消耗。 |
输入示例 |
4 5 1 0 1 0 10 10 100 10 5 20 15 10 1 2 30 2 3 40 1 3 20 1 4 200 3 4 200 |
输出示例 |
130 |
其他说明 |
【数据范围】 对于30%的数据： 1<=N<=100,1<=M<=500 对于60%的数据： 1<=N<=1000,1<=M<=5000 对于100%的数据： 1<=N<=5000，1<=M<=30000 其中20%的数据为1<=N<=3000的链 1<=u,v<=N, 1<=k,w[i],s[i]<=200 【样例说明】 按照1->3->4的路线。 |
将一个点拆成两个点，分别是奇数秒和偶数秒第i个点，然后各种连边最短路即可。
#include<cstdio>
#include<cctype>
#include<queue>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i;i=next[i])
using namespace std;
inline int read() {
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
const int maxm=;
const int INF=;
struct Dijkstra {
int n,m,first[maxn],next[maxm];
struct Edge {int to,dist;}edges[maxm];
int done[maxn],d[maxn];
struct HeapNode {
int u,d;
bool operator < (const HeapNode& ths) const {return d>ths.d;}
};
void init(int n) {
this->n=n;m=;
memset(first,,sizeof(first));
}
void AddEdge(int u,int v,int w) {
//printf("%d --> %d %d\n",u,v,w);
edges[++m]=(Edge){v,w};next[m]=first[u];first[u]=m;
}
void solve(int s) {
rep(i,,n) d[i]=INF,done[i]=;
priority_queue<HeapNode> Q;
Q.push((HeapNode){s,});d[s]=;
while(!Q.empty()) {
int x=Q.top().u;Q.pop();
if(done[x]) continue;done[x]=;
ren {
Edge& e=edges[i];
if(d[e.to]>d[x]+e.dist) {
d[e.to]=d[x]+e.dist;
Q.push((HeapNode){e.to,d[e.to]});
}
}
}
}
}sol;
//1---n 0 n+1----2*n 1
int n,m,type[maxn],w[maxn],s[maxn],u[maxn*],v[maxn*],k[maxn*];
int first[maxn],next[maxn*];
void Add(int x,int v) {
next[v]=first[x];first[x]=v;
}
int main() {
n=read();m=read();
rep(i,,n) type[i]=read();
rep(i,,n) w[i]=read();
rep(i,,n) s[i]=read();
rep(i,,m) u[i]=read(),v[i]=read(),k[i]=read(),Add(u[i],i);
sol.init(n*);
rep(x,,n*) {
if(x<=n) sol.AddEdge(x,x+n,type[x]*s[x]);
else sol.AddEdge(x,x-n,(type[x-n]^)*s[x-n]);
if(x<=n) ren {
if(type[x]==type[v[i]]) sol.AddEdge(x,v[i]+n,k[i]);
else if(type[x]) sol.AddEdge(x,v[i]+n,k[i]+abs(w[x]-w[v[i]]));
else sol.AddEdge(x,v[i]+n,max(,k[i]-abs(w[x]-w[v[i]])));
}
else for(int i=first[x-n];i;i=next[i]) {
if(type[x-n]==type[v[i]]) sol.AddEdge(x,v[i],k[i]);
else if(type[x-n]) sol.AddEdge(x,v[i],max(,k[i]-abs(w[x-n]-w[v[i]])));
else sol.AddEdge(x,v[i],k[i]+abs(w[x-n]-w[v[i]]));
}
}
sol.solve();
printf("%d\n",min(sol.d[n],sol.d[n*]));
return ;
}
| 双色球 |
| 难度级别：C； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
试题描述 |
机房来了新一届的学弟学妹，邪恶的chenzeyu97发现一位学弟与他同名，于是他当起了善良的学长233 “来来来，学弟，我考你道水题检验一下你的水平……” 一个栈内初始有n个红色和蓝色的小球，请你按照以下规则进行操作 1. 只要栈顶的小球是红色的，将其取出，直到栈顶的球是蓝色 2. 然后将栈顶的蓝球变成红色 3. 最后放入若干个蓝球直到栈中的球数为n 以上3步骤为一次操作 如栈中都是红色球，则操作停止，请问几次操作后停止 chenzeyu97出完题发现他自己不能AC所以想请你帮忙 |
输入 |
第一行为一个整数n，表示栈的容量为n 第二行为一个字符串，第i个字符表示自顶向下的第i个球的颜色，R代表红色，B代表蓝色 |
输出 |
一个整数表示操作数 |
输入示例 |
10 BRRRRRRRRR |
输出示例 |
1 |
其他说明 |
50%的数据，1<=n<=20 100%的数据，1<=n<=50 |
发现将RRRRRR--B变成RRRRRR--R需要2^n次操作。
n个R
#include<cstdio>
#include<cctype>
#include<queue>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i!=-1;i=next[i])
using namespace std;
inline int read() {
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
char s[];
int main() {
int n=read();
long long ans=;
scanf("%s",s);
rep(i,,n-) ans|=(1ll<<i)*(s[i]=='B');
printf("%lld\n",ans);
return ;
}
| 魔方 |
| 难度级别：C； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
试题描述 |
ccy（ndsf）觉得手动复原魔方太慢了，所以他要借助计算机。 ccy（ndsf）家的魔方都是3*3*3的三阶魔方，大家应该都见过。 （3的“顺时针”改为“逆时针”，即3 4以图为准。） 输入数据观察角度说明图： |
输入 |
第一行，一串数字，表示从网上搜到的攻略。 下面6*3行，每行3个数字，每三行表示魔方一个面的情况，六个面的顺序是前、后、左、右、上、下。 |
输出 |
6*3行，表示处理后的魔方，形式同输入。 |
输入示例 |
23 121 221 111 123 321 111 123 321 132 132 231 132 121 112 233 332 111 333 |
输出示例 |
123 222 113 212 121 211 323 321 132 121 333 121 131 213 112 331 111 331 |
其他说明 |
40%的数据，攻略的长度小于5且仅有4种操作的其中一种 100%的数据，攻略的长度小于100 |
恩，问LZJ吧。
#include<iostream>
#include<cstdio>
#define front 0
#define back 1
#define left 2
#define right 3
#define up 4
#define down 5
using namespace std;
char order[];
struct Cube
{
int block[][][];
void Rotate(int n)
{
Cube b=*this;
if(n==)
{
b.block[up][][]=block[front][][];
b.block[up][][]=block[front][][];
b.block[up][][]=block[front][][];
b.block[front][][]=block[down][][];
b.block[front][][]=block[down][][];
b.block[front][][]=block[down][][];
b.block[back][][]=block[up][][];
b.block[back][][]=block[up][][];
b.block[back][][]=block[up][][];
b.block[down][][]=block[back][][];
b.block[down][][]=block[back][][];
b.block[down][][]=block[back][][];
b.block[right][][]=block[right][][];
b.block[right][][]=block[right][][];
b.block[right][][]=block[right][][];
b.block[right][][]=block[right][][];
b.block[right][][]=block[right][][];
b.block[right][][]=block[right][][];
b.block[right][][]=block[right][][];
b.block[right][][]=block[right][][];
}
else if(n==)
{
b.Rotate();
b.Rotate();
b.Rotate();
}
else if(n==)
{
b.block[left][][]=block[back][][];
b.block[left][][]=block[back][][];
b.block[left][][]=block[back][][];
b.block[back][][]=block[right][][];
b.block[back][][]=block[right][][];
b.block[back][][]=block[right][][];
b.block[right][][]=block[front][][];
b.block[right][][]=block[front][][];
b.block[right][][]=block[front][][];
b.block[front][][]=block[left][][];
b.block[front][][]=block[left][][];
b.block[front][][]=block[left][][];
b.block[up][][]=block[up][][];
b.block[up][][]=block[up][][];
b.block[up][][]=block[up][][];
b.block[up][][]=block[up][][];
b.block[up][][]=block[up][][];
b.block[up][][]=block[up][][];
b.block[up][][]=block[up][][];
b.block[up][][]=block[up][][];
}
else if(n==)
{
b.Rotate();
b.Rotate();
b.Rotate();
}
*this=b;
}
}C;
int main()
{
int c;
scanf("%s",order);
for(int i=;i<;i++)
for(int x=;x<;x++)
for(int y=;y<;y++)
{
c=getchar();
while(!isdigit(c))c=getchar();
C.block[i][y][x]=c-'';
}
for(int i=,len=strlen(order);i<len;i++)
{
C.Rotate(order[i]-'');
}
for(int i=;i<;i++)
for(int x=;x<;x++)
{
for(int y=;y<;y++)
printf("%d",C.block[i][y][x]);
putchar('\n');
}
}
| czy的后宫 |
| 难度级别：C； 运行时间限制：3000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
试题描述 |
czy要妥善安排他的后宫，他想在机房摆一群妹子，一共有n个位置排成一排，每个位置可以摆妹子也可以不摆妹子。有些类型妹子如果摆在相邻的位置（隔着一个空的位置不算相邻），就不好看了。假定每种妹子数量无限，求摆妹子的方案数。 |
输入 |
输入有m+1行，第一行有两个用空格隔开的正整数n、m，m表示妹子的种类数。接下来的m行，每行有m个字符1或0,若第i行第j列为1，则表示第i种妹子第j种妹子不能排在相邻的位置，输入保证对称。（提示：同一种妹子可能不能排在相邻位置）。 |
输出 |
输出只有一个整数，为方案数（这个数字可能很大，请输出方案数除以1000000007的余数。 |
输入示例 |
2 2 01 10 |
输出示例 |
7 |
其他说明 |
【样例说明】 七种方案为(空，空)、（空，1）、（1、空）、（2、空）、（空、2）、（1,1）、（2,2）。 【数据范围】 20%的数据，1＜n≤5,0＜m≤10。 60%的数据，1＜n≤200,0＜m≤100。 100%的数据，1＜n≤1000000000，0＜m≤100。 注：此题时限1.5s是因为本评测机跑太慢，大家正常做 但写的太丑可能T一俩个点 |
将空格视为一种新的MZ，设f[i][k]表示已放了i个MZ，最后一个MZ种类为k的方案数，然后用矩阵快速幂优化。
#include<cstdio>
#include<cctype>
#include<queue>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i!=-1;i=next[i])
using namespace std;
inline int read() {
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
const int MOD=;
typedef long long ll;
int n,m;
struct Matrix {
ll A[maxn][maxn];
Matrix() {memset(A,,sizeof(A));}
Matrix operator * (const Matrix& b) const {
Matrix c;
rep(i,,m) rep(j,,m) {
c.A[i][j]=;
rep(k,,m) (c.A[i][j]+=A[i][k]*b.A[k][j])%=MOD;
}
return c;
}
void print() {
rep(i,,m) {
rep(j,,m) printf("%lld ",A[i][j]);
puts("");
}
}
};
void pow(Matrix& ans,int n) {
Matrix t=ans;n--;
while(n) {
if(n&) ans=ans*t;
t=t*t;n>>=;
}
}
char s[maxn];
int main() {
Matrix ans;
n=read();m=read();
rep(i,,m) {
scanf("%s",s+);
rep(j,,m) ans.A[i][j]=(s[j]=='');
}
m++;rep(i,,m) ans.A[i][m]=ans.A[m][i]=;
pow(ans,n);
ll res=;
rep(i,,m) (res+=ans.A[m][i])%=MOD;
printf("%lld\n",res);
return ;
}
| 护花 |
| 难度级别：C； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
试题描述 |
约翰留下他的N(N<=100000)只奶牛上山采木．他离开的时候，她们像往常一样悠闲地在草场里吃草．可是，当他回来的时候，他看到了一幕惨剧：牛们正躲在他的花园里，啃食着他心爱的美丽花朵！为了使接下来花朵的损失最小，约翰赶紧采取行动，把牛们送回牛棚． 牛们从1到N编号．第i只牛所在的位置距离牛棚Ti(1≤Ti≤2000000)分钟的路程，而在约翰开始送她回牛棚之前，她每分钟会啃食Di(1≤Di≤100)朵鲜花．无论多么努力，约翰一次只能送一只牛回棚．而运送第第i只牛事实上需要2Ti分钟，因为来回都需要时间． 写一个程序来决定约翰运送奶牛的顺序，使最终被吞食的花朵数量最小． |
输入 |
第1行输入N，之后N行每行输入两个整数Ti和Di |
输出 |
一个整数，表示最小数量的花朵被吞食 |
输入示例 |
6 3 1 2 5 2 3 3 2 4 1 1 6 |
输出示例 |
86 |
其他说明 |
【样例解释】 约翰用6，2，3，4，1，5的顺序来运送他的奶牛 |
与国王游戏类似，用相邻交换法自己证吧。
#include<cstdio>
#include<cctype>
#include<queue>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i!=-1;i=next[i])
using namespace std;
inline int read() {
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
typedef long long ll;
const int maxn=;
struct Cow {
int t,d;
bool operator < (const Cow& ths) const {return d*ths.t>ths.d*t;}
}A[maxn];
int n;
ll ans,all;
int main() {
n=read();
rep(i,,n) A[i].t=read(),A[i].d=read(),all+=A[i].d;
sort(A+,A+n+);
rep(i,,n) {
all-=A[i].d;
ans+=all*A[i].t;
}
printf("%lld\n",ans*);
return ;
}
| 修剪草坪 |
| 难度级别：C； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
试题描述 |
在一年前赢得了小镇的最佳草坪比赛后，FJ变得很懒，再也没有修剪过草坪。现在， |
输入 |
* 第一行：空格隔开的两个整数N和K * 第二到N+1行：第i+1行有一个整数E_i |
输出 |
* 第一行：一个值，表示FJ可以得到的最大的效率值。 |
输入示例 |
5 2 1 2 3 4 5 |
输出示例 |
12 |
其他说明 |
输入解释： FJ有5只奶牛，他们的效率为1，2，3，4，5。他们希望选取效率总和最大的奶牛，但是 他不能选取超过2只连续的奶牛 FJ可以选择出了第三只以外的其他奶牛，总的效率为1+2+4+5=12。 |
设f[i]表示前i头奶牛最少浪费的效率和，转移时用个单调队列即可。
#include<cstdio>
#include<cctype>
#include<queue>
#include<cstring>
#include<algorithm>
#define rep(s,t) for(int i=s;i<=t;i++)
#define ren for(int i=first[x];i!=-1;i=next[i])
using namespace std;
inline int read() {
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
int n,k,A[maxn];
int q[maxn],l,r;
long long f[maxn],ans,mn=1ll<<;
int main() {
n=read();k=read();
rep(,n) A[i]=read(),ans+=A[i];
int l=,r=;
rep(,n) {
while(l<=r&&f[q[r]]>=f[i-]) r--;q[++r]=i-;
while(l<=r&&q[l]<i-k-) l++;
f[i]=f[q[l]]+A[i];
}
rep(n-k,n) mn=min(mn,f[i]);
printf("%lld\n",ans-mn);
return ;
}
| 虫洞 |
| 难度级别：C； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
试题描述 |
John在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边，并可以使你返回到过去的一个时刻（相对你进入虫洞之前）。John的每个农场有M条小路（无向边）连接着N （从1..N标号）块地，并有W个虫洞（有向边）。其中1<=N<=500,1<=M<=2500,1<=W<=200。 现在John想借助这些虫洞来回到过去（出发时刻之前），请你告诉他能办到吗。 John将向你提供F(1<=F<=5)个农场的地图。没有小路会耗费你超过10000秒的时间，当然也没有虫洞回帮你回到超过10000秒以前。 |
输入 |
* Line 1: 一个整数 F, 表示农场个数。 * Line 1 of each farm: 三个整数 N, M, W。 * Lines 2..M+1 of each farm: 三个数（S, E, T）。表示在标号为S的地与标号为E的地中间有一条用时T秒的小路。 * Lines M+2..M+W+1 of each farm: 三个数（S, E, T）。表示在标号为S的地与标号为E的地中间有一条可以使John到达T秒前的虫洞。 |
输出 |
* Lines 1..F: 如果John能在这个农场实现他的目标，输出"YES",否则输出"NO"。 |
输入示例 |
2 3 3 1 1 2 2 1 3 4 2 3 1 3 1 3 3 2 1 1 2 3 2 3 4 3 1 8 |
输出示例 |
NO YES |
判负环用DFS版的SPFA比较优美。
#include<cstdio>
#include<cctype>
#include<queue>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i;i=next[i])
using namespace std;
inline int read() {
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
const int maxm=;
struct SPFA {
int n,m,ok,first[maxn],next[maxm];
void init(int n) {
this->n=n;m=;ok=;
fill(first+,first+n+,);
}
struct Edge {int to,dist;}edges[maxm];
void AddEdge(int u,int v,int w) {
edges[++m]=(Edge){v,w};next[m]=first[u];first[u]=m;
}
int vis[maxn],d[maxn];
int spfa(int x) {
vis[x]=;
ren {
Edge& e=edges[i];
if(d[e.to]>d[x]+e.dist) {
if(vis[e.to]) return ;
else {
d[e.to]=d[x]+e.dist;
if(spfa(e.to)) return ;
}
}
}
vis[x]=;
return ;
}
int solve() {
rep(i,,n) d[i]=vis[i]=;
rep(i,,n) if(spfa(i)) return ;
return ;
}
}sol;
int main() {
int T=read();
while(T--) {
int n=read(),m=read(),w=read(),a,b,c;
sol.init(n);
rep(i,,m) {
a=read();b=read();c=read();
sol.AddEdge(a,b,c);sol.AddEdge(b,a,c);
}
rep(i,,w) {
a=read();b=read();c=read();
sol.AddEdge(a,b,-c);
}
puts(sol.solve()?"YES":"NO");
}
return ;
}
| 水灾 |
| 难度级别：C； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
试题描述 |
已经连续下了几天雨，却还是没有停的样子。土豪CCY刚从外地赚完1e元回来，知道不久除了自己别墅，其他的地方都将会被洪水淹没。 CCY所在的城市可以用一个N*M(N,M<=50)的地图表示，地图上有五种符号：“. * X D S”。其中“X”表示石头，水和人都不能从上面经过。“.”表示平原，CCY和洪水都可以经过。“*”表示洪水开始地方（可能有多个地方开始发生洪水）。“D”表示CCY的别墅。“S”表示CCY现在的位置。 CCY每分钟可以向相邻位置移动，而洪水将会在CCY移动之后把相邻的没有的土地淹没（从已淹没的土地）。 求CCY回到别墅的最少时间。如果聪哥回不了家，就很可能会被淹死，那么他就要膜拜黄金大神涨RP来呼叫直升飞机，所以输出“ORZ hzwer!!!”。 |
输入 |
第一行：N和M 接下来N行，每行M个字符，表示地图。 |
输出 |
若能回家，输出一个整数，表示最少回家步数；否则输出“ORZ hzwer!!!”。 |
输入示例 |
3 3 D.* ... .S. |
输出示例 |
3 |
只要CCY比洪水到达的时间早就可以走，两遍BFS即可。
#include<cstdio>
#include<cctype>
#include<queue>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i!=-1;i=next[i])
using namespace std;
inline int read() {
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
const int mmx[]={,-,,};
const int mmy[]={,,-,};
char s[maxn][maxn];
int n,m,X0,Y0;
queue<int> Q;
int vis[maxn][maxn],Time[maxn][maxn];
void bfs1() {
memset(vis,,sizeof(vis));
rep(i,,n-) rep(j,,m-) {
Time[i][j]=<<;
if(s[i][j]=='*') {
vis[i][j]=;Q.push(i*m+j);Time[i][j]=;
}
else if(s[i][j]=='S') {
X0=i;Y0=j;
}
}
while(!Q.empty()) {
int x=Q.front()/m,y=Q.front()%m;Q.pop();
rep(dir,,) {
int mx=x+mmx[dir],my=y+mmy[dir];
if(mx>=&&mx<n&&my>=&&my<m&&s[mx][my]!='D'&&s[mx][my]!='X'&&!vis[mx][my]) {
vis[mx][my]=;
Time[mx][my]=Time[x][y]+;
Q.push(mx*m+my);
}
}
}
}
int d[maxn][maxn];
void bfs(int x,int y) {
memset(vis,,sizeof(vis));
Q.push(x*m+y);vis[x][y]=;
while(!Q.empty()) {
x=Q.front()/m,y=Q.front()%m;Q.pop();
if(s[x][y]=='D') {printf("%d\n",d[x][y]);return;}
rep(dir,,) {
int mx=x+mmx[dir],my=y+mmy[dir];
if(mx>=&&mx<n&&my>=&&my<m&&d[x][y]+<Time[mx][my]&&s[mx][my]!='X'&&!vis[mx][my]) {
vis[mx][my]=;
d[mx][my]=d[x][y]+;
Q.push(mx*m+my);
}
}
}
puts("ORZ hzwer!!!");
}
int main() {
n=read();m=read();
rep(i,,n-) scanf("%s",s[i]);
bfs1();
bfs(X0,Y0);
return ;
}
| 某种数列问题 |
| 难度级别：C； 运行时间限制：1000ms； 运行空间限制：262144KB； 代码长度限制：2000000B |
试题描述 |
众所周知，chenzeyu97有无数的妹子(阿掉！>_<)，而且他还有很多恶趣味的问题，继上次纠结于一排妹子的排法以后，今天他有非(chi)常(bao)认(cheng)真(zhe)去研究一个奇怪的问题。有一堆他的妹子站成一排，然后对于每个妹子有一个美丽度，当然美丽度越大越好，chenzeyu97妹子很多，但是质量上不容乐观，经常出现很多美丽度为负数的妹子(喜闻乐见)，chenzeyu97希望从一排妹子里找出3队连续的妹子，使她们的美丽度和最大。注意，一个妹子不能被编入多个队伍而且一定要拿出三队，不然czy会闲着没事做~。 简单滴说就是： 给定一个数列，从中找到3个无交集的连续子数列使其和最大。 |
输入 |
第一行一个数n，表示数列长度。 接下来有n行，每行一个数，第i行为第i个数。 |
输出 |
仅有一个数，表示最大和。 |
输入示例 |
10 -1 2 3 -4 0 1 -6 -1 1 -2 |
输出示例 |
7 |
其他说明 |
【样例说明】 第一队妹子取2，3。 第二队妹子取0，1。 第三队妹子取1。 【数据范围】 |
枚举最后一段的起点，那么只要算前缀选出2段即可，具体看代码。
#include<cstdio>
#include<cctype>
#include<queue>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i!=-1;i=next[i])
using namespace std;
inline int read() {
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
typedef long long ll;
const int maxn=;
const ll INF=1ll<<;
int n;
ll A[maxn],S[maxn];
ll f[maxn],g[maxn];
void getf() {
ll mn=;f[]=-INF;
rep(i,,n) f[i]=max(f[i-],S[i]-mn),mn=min(mn,S[i]);
}
void getg() {
ll mx=;g[]=-INF;
rep(i,,n) {
if(i!=) g[i]=max(g[i-],S[i]+mx);
else g[i]=-INF;
mx=max(mx,(f[i]-S[i]));
//printf("%lld ",g[i]);
}
//puts("");
}
void getans() {
ll mx=S[n],ans=-INF;
dwn(i,n,) {
ans=max(ans,g[i-]+mx-S[i-]);
mx=max(mx,S[i-]);
}
printf("%lld\n",ans);
}
int main() {
n=read();
rep(i,,n) A[i]=read(),S[i]=S[i-]+A[i];
getf();getg();getans();
return ;
}
/*
4
-1 -2 1 -3
*/
| 密码锁 |
| 难度级别：C； 运行时间限制：1000ms； 运行空间限制：262144KB； 代码长度限制：2000000B |
试题描述 |
hzwer有一把密码锁，由N个开关组成。一开始的时候，所有开关都是关上的。当且仅当开关x1,x2,x3,...xk为开，其他开关为关时，密码锁才会打开。 他可以进行M种的操作，每种操作有一个size[i]，表示，假如他选择了第i种的操作的话，他可以任意选择连续的size[i]个格子，把它们全部取反。（注意，由于黄金大神非常的神，所以操作次数可以无限>_<） 本来这是一个无关紧要的问题，但是，黄金大神不小心他的钱丢进去了，没有的钱他哪里能逃过被chenzeyu97 NTR的命运？>_< 于是，他为了虐爆czy，也为了去泡更多的妹子，决定打开这把锁。但是他那么神的人根本不屑这种”水题”。于是，他找到了你。 你的任务很简单，求出最少需要多少步才能打开密码锁，或者如果无解的话，请输出-1。 |
输入 |
第1行，三个正整数N，K，M，如题目所述。 第2行，K个正整数，表示开关x1,x2,x3..xk必须为开，保证x两两不同。 第三行，M个正整数，表示size[i]，size[]可能有重复元素。 |
输出 |
输出答案，无解输出-1。 |
输入示例 |
10 8 2 1 2 3 5 6 7 8 9 3 5 |
输出示例 |
2 |
其他说明 |
对于50%的数据，1≤N≤20，1≤k≤5，1≤m≤3; 对于另外20%的数据，1≤N≤10000，1≤k≤5,1≤m≤30; 对于100%的数据，1≤N≤10000，1≤k≤10，1≤m≤100。 |
这应该是这几道题中质量最高的题了，本蒟蒻并没有自己想出来。
注意到题目中的是区间修改，把沿途的位置取反，这个可以看做是在模2意义下，给区间的加一操作。在我们通常的思路中，对于区间的操作，原本是要修改区间长度个的位置的情况，我们都可以通过考虑它的差分序列，使得要修改的位置个数变成2个，我们要求最少的修改，使得原序列变成全0。
所以对原序列进行差分，那么每次修改就是要你对i号位置和i+size[]模2意义下的加1。
差分后的序列中，数值为1的个数是不会超过2k个，即不会超过20个。
考虑每次对i和i+x改动的过程，如果原序列中，i号位置和i+x号位置都是0的话，我们这么改，没有任何必要。所以任意时刻，数值为1的位置个数是不会增加的，那么我们可以把每一个的1看成一个的石子，那么每次我们可以把石子往某个方向移动size[]步，如果移动之后的位置存在石子的话，就对对碰，消掉了。
因为是对对碰，石子之间的关系肯定是一个匹配的关系，我们不妨求出Dist[i][j]表示，石子i要走到石子j的位置，至少需要移动多少步，那么我们可以枚举每一个石子，然后进行一遍的bfs即可，这一部分的复杂度是O(2kmn)。
现在问题转化为有一个大小不超过20的完全图，我们想要求它的最小权最大匹配。
可以用状态压缩DP，设f[S]表示集合S的最小划分代价，每次选出最小的元素作为匹配元素之一，枚举另一个元素即可。
#include<cstdio>
#include<cctype>
#include<queue>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i!=-1;i=next[i])
using namespace std;
inline int read() {
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int INF=<<;
int n,k,m,cnt,A[],num[],e[][],s[];
queue<int> Q;
int vis[],d[];
int f[<<];
void bfs(int x,int id) {
memset(vis,,sizeof(vis));
Q.push(x);vis[x]=;d[x]=;
while(!Q.empty()) {
x=Q.front();Q.pop();
rep(i,,m) {
if((x+s[i])<=n&&!vis[x+s[i]]) {
vis[x+s[i]]=;d[x+s[i]]=d[x]+;Q.push(x+s[i]);
}
if((x-s[i])>=&&!vis[x-s[i]]) {
vis[x-s[i]]=;d[x-s[i]]=d[x]+;Q.push(x-s[i]);
}
}
}
rep(i,,cnt) {
if(vis[num[i]]) e[id][i]=d[num[i]];
else e[id][i]=INF;
}
}
int main() {
n=read();k=read();m=read();
rep(i,,k) A[read()]=;
rep(i,,m) s[i]=read();
dwn(i,++n,) A[i]^=A[i-];
rep(i,,n) if(A[i]) A[i]=++cnt,num[cnt]=i;
rep(i,,n) if(A[i]) bfs(i,A[i]);
rep(S,,(<<cnt)-) f[S]=INF;
rep(S,,(<<cnt)-) {
int j;
rep(k,,cnt) if((<<k-)&S) {j=k;break;}
rep(k,,cnt) if((<<k-)&S) {
f[S]=min(f[S],f[S^(<<j-)^(<<k-)]+e[j][k]);
}
}
printf("%d\n",f[(<<cnt)-]==INF?-:f[(<<cnt)-]);
return ;
}
| 抓牛 |
| 难度级别：C； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
试题描述 |
农夫约翰被通知，他的一只奶牛逃逸了！所以他决定，马上出发，尽快把那只奶牛抓回来． 他们都站在数轴上．约翰在N(O≤N≤100000)处，奶牛在K(O≤K≤100000)处．约翰有两种办法移动，步行和瞬移：步行每秒种可以让约翰从x处走到x+1或x-1处；而瞬移则可让他在1秒内从x处消失，在2x处出现．然而那只逃逸的奶牛，悲剧地没有发现自己的处境多么糟糕，正站在那儿一动不动． 那么，约翰需要多少时间抓住那只牛呢？ |
输入 |
仅有两个整数N和K |
输出 |
最短时间 |
输入示例 |
5 17 |
输出示例 |
4 |
直接BFS即可。
#include<cstdio>
#include<cctype>
#include<queue>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i!=-1;i=next[i])
using namespace std;
inline int read() {
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
queue<int> Q;
int d[maxn],vis[maxn];
void bfs(int s,int t) {
swap(s,t);
vis[s]=;Q.push(s);
while(!Q.empty()) {
int x=Q.front();Q.pop();
if(x==t) {printf("%d\n",d[x]);return;}
if(x>=&&!vis[x-]) {
d[x-]=d[x]+;
vis[x-]=;
Q.push(x-);
}
if(x<=&&!vis[x+]) {
d[x+]=d[x]+;
vis[x+]=;
Q.push(x+);
}
if(x*<=&&!vis[x*]) {
d[x<<]=d[x]+;
vis[x<<]=;
Q.push(x<<);
}
}
}
int main() {
bfs(read(),read());
return ;
}
| 路面修整 |
| 难度级别：C； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
试题描述 |
FJ打算好好修一下农场中某条凹凸不平的土路。按奶牛们的要求，修好后的路面高度应当单调上升或单调下降，也就是说，高度上升与高度下降的路段不能同时出现在修好的路中。 整条路被分成了N段，N个整数A_1, ... , A_N (1 <= N <= 2,000)依次描述了每一段路的高度(0 <= A_i <= 1,000,000,000)。FJ希望找到一个恰好含N个元素的不上升或不下降序列B_1, ... , B_N，作为修过的路中每个路段的高度。由于将每一段路垫高或挖低一个单位的花费相同，修路的总支出可以表示为： |A_1 - B_1| + |A_2 - B_2| + ... + |A_N - B_N| 请你计算一下，FJ在这项工程上的最小支出是多少。FJ向你保证，这个支出不会超过2^31-1。 |
输入 |
第1行: 输入1个整数：N 第2..N+1行: 第i+1行为1个整数：A_i |
输出 |
第1行: 输出1个正整数，表示FJ把路修成高度不上升或高度不下降的最小花费 |
输入示例 |
7 1 3 2 4 5 3 9 |
输出示例 |
3 |
其他说明 |
【样例解释】 FJ将第一个高度为3的路段的高度减少为2，将第二个高度为3的路段的高度增加到5，总花费为|2-3|+|5-3| = 3，并且各路段的高度为一个不下降序列 1,2,2,4,5,5,9。 |
先离散，然后DP两遍。
以算单调递增为例，设f[i][k]表示前i段路已符合要求，并且第i段路修到了k高度的最小代价。f[i][k]=min(f[i][k-1],f[i-1][j]+|Ai-Bk|)
#include<cstdio>
#include<cctype>
#include<queue>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i!=-1;i=next[i])
using namespace std;
inline int read() {
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
typedef long long ll;
const int maxn=;
int n,A[maxn],B[maxn];
ll f[maxn][maxn];
int main() {
n=read();
rep(i,,n) B[i]=A[i]=read(),f[i][]=1ll<<;
sort(B+,B+n+);
rep(i,,n) rep(j,,n) f[i][j]=min(f[i][j-],f[i-][j]+abs(B[j]-A[i]));
ll ans=f[n][n];
rep(i,,n) rep(j,,n) f[i][j]=min(f[i][j-],f[i-][j]+abs(B[n-j+]-A[i]));
printf("%lld\n",min(ans,f[n][n]));
return ;
}
| 教主的魔法 |
| 难度级别：C； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
试题描述 |
教主最近学会了一种神奇的魔法，能够使人长高。于是他准备演示给XMYZ信息组每个英雄看。于是N个英雄们又一次聚集在了一起，这次他们排成了一列，被编号为1、2、……、N。 每个人的身高一开始都是不超过1000的正整数。教主的魔法每次可以把闭区间[L, R]（1≤L≤R≤N）内的英雄的身高全部加上一个整数W。（虽然L=R时并不符合区间的书写规范，但我们可以认为是单独增加第L（R）个英雄的身高） CYZ、光哥和ZJQ等人不信教主的邪，于是他们有时候会问WD闭区间 [L, R] 内有多少英雄身高大于等于C，以验证教主的魔法是否真的有效。 WD巨懒，于是他把这个回答的任务交给了你。 |
输入 |
第1行为两个整数N、Q。Q为问题数与教主的施法数总和。 第2行有N个正整数，第i个数代表第i个英雄的身高。 第3到第Q+2行每行有一个操作： （1）若第一个字母为“M”，则紧接着有三个数字L、R、W。表示对闭区间 [L, R] 内所有英雄的身高加上W。 （2）若第一个字母为“A”，则紧接着有三个数字L、R、C。询问闭区间 [L, R] 内有多少英雄的身高大于等于C。 |
输出 |
对每个“A”询问输出一行，仅含一个整数，表示闭区间 [L, R] 内身高大于等于C的英雄数。 |
输入示例 |
5 3 1 2 3 4 5 A 1 5 4 M 3 5 1 A 1 5 4 |
输出示例 |
2 3 |
其他说明 |
【输入输出样例说明】 原先5个英雄身高为1、2、3、4、5，此时[1, 5]间有2个英雄的身高大于等于4。教主施法后变为1、2、4、5、6，此时[1, 5]间有3个英雄的身高大于等于4。 【数据范围】 对30%的数据，N≤1000，Q≤1000。 对100%的数据，N≤1000000，Q≤3000，1≤W≤1000，1≤C≤1,000,000,000 |
分块打标记即可，经典问题。
#include<cctype>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
inline void read(int& x)
{
char ch=getchar();x=;
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=x*+ch-'',ch=getchar();
}
const int maxn=;
int n,m,SIZE,bl[maxn],st[maxn],en[maxn],A[maxn],B[maxn],add[maxn];
void reset(int x)
{
for(int i=st[x];i<=en[x];i++) B[i]=A[i];
sort(B+st[x],B+en[x]+);
/*for(int i=st[x];i<=en[x];i++) printf("%d ",B[i]);
printf(" %d\n",x);*/
}
int query(int x,int v)
{
if(B[st[x]]>v) return ;
int L=st[x],R=en[x]+;
while(R-L>)
{
int M=L+R>>;
if(B[M]<=v) L=M;
else R=M;
}
return L-st[x]+;
}
int main()
{
read(n);read(m);SIZE=(int)sqrt(n);
for(int i=;i<=n;i++)
{
read(A[i]);A[i]=-A[i];
bl[i]=(i-)/SIZE+;
if(!st[bl[i]]) st[bl[i]]=i;
en[bl[i]]=i;
}
for(int i=;i<=bl[n];i++) reset(i);
int L,R,v,ans;
while(m--)
{
char tp[];scanf("%s",tp);
read(L),read(R),read(v);v=-v;
if(tp[]=='A')
{
ans=;
for(int i=bl[L]+;i<bl[R];i++) ans+=query(i,v-add[i]);
if(bl[L]!=bl[R])
{
for(int i=L;i<=en[bl[L]];i++) if(A[i]+add[bl[L]]<=v) ans++;
for(int i=st[bl[R]];i<=R;i++) if(A[i]+add[bl[R]]<=v) ans++;
}
else for(int i=L;i<=R;i++) if(A[i]+add[bl[L]]<=v) ans++;
printf("%d\n",ans);
}
else
{
if(bl[L]!=bl[R])
{
for(int i=bl[L]+;i<bl[R];i++) add[i]+=v;
for(int i=L;i<=en[bl[L]];i++) A[i]+=v;
for(int i=st[bl[R]];i<=R;i++) A[i]+=v;
reset(bl[L]); reset(bl[R]);
}
else
{
for(int i=L;i<=R;i++) A[i]+=v;
reset(bl[L]);
}
}
}
return ;
}
| 吃豆豆 |
| 难度级别：C； 运行时间限制：5000ms； 运行空间限制：262144KB； 代码长度限制：2000000B |
试题描述 |
两个PACMAN吃豆豆。一开始的时候，PACMAN都在坐标原点的左下方，豆豆都在右上方。PACMAN走到豆豆处就会吃掉它。PACMAN行走的路线很奇怪，只能向右走或者向上走，他们行走的路线不可以相交。 请你帮这两个PACMAN计算一下，他们两加起来最多能吃掉多少豆豆。 |
输入 |
第一行为一个整数N，表示豆豆的数目。接下来N行，每行一对正整数Xi，Yi，表示第i个豆豆的坐标。任意两个豆豆的坐标都不会重合。 |
输出 |
仅有一行包含一个整数，即两个PACMAN加起来最多能吃掉的豆豆数量。 |
输入示例 |
8 8 1 1 5 5 7 2 2 7 8 4 6 3 3 6 4 |
输出示例 |
7 |
其他说明 |
对于30%的数据，1<=N<=25； 对于70%的数据，1<=N<=500； 对于100%的数据，1<=N<=2000,1<=Xi ，Yi <=200000 ； |
似乎有DP的做法？？？
这里是费用流的解法：可以发现两个PACMAN的路线总不会交叉的，那么问题转化为点容量为1的费用流。
#include<cstdio>
#include<cctype>
#include<queue>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i!=-1;i=next[i])
using namespace std;
inline int read() {
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
const int maxm=;
const int INF=;
struct ZKW {
int n,m,s,t,ans,cost;
int first[maxn],next[maxm];
struct Edge {int from,to,flow,cost;}edges[maxm];
void init(int n) {
this->n=n;m=;
memset(first,-,sizeof(first));
}
void AddEdge(int u,int v,int cap,int cost) {
edges[m]=(Edge){u,v,cap,cost};next[m]=first[u];first[u]=m++;
edges[m]=(Edge){v,u,,-cost};next[m]=first[v];first[v]=m++;
}
int d[maxn],vis[maxn],inq[maxn];
int dfs(int x,int a) {
if(x==t||!a) {ans+=a*cost;return a;}
vis[x]=;int flow=,f;
ren {
Edge& e=edges[i];
if(!e.cost&&e.flow&&!vis[e.to]&&(f=dfs(e.to,min(a,e.flow)))) {
e.flow-=f;edges[i^].flow+=f;
flow+=f;a-=f;if(!a) break;
}
}
return flow;
}
int bfs() {
queue<int> Q;rep(i,,n) d[i]=INF;
d[t]=;inq[t]=;Q.push(t);
while(!Q.empty()) {
int x=Q.front();Q.pop();inq[x]=;
//printf("%d %d\n",x,d[x]);
ren {
Edge& e=edges[i^];
if(e.flow&&d[e.from]>d[x]+e.cost) {
d[e.from]=d[x]+e.cost;
if(!inq[e.from]) inq[e.from]=,Q.push(e.from);
}
}
}
rep(i,,m-) edges[i].cost+=d[edges[i].to]-d[edges[i].from];
cost+=d[s];return d[s]!=INF;
}
int solve(int s,int t) {
this->s=s;this->t=t;ans=cost=;
while(bfs()) do memset(vis,,sizeof(vis));while(dfs(s,INF));
return ans;
}
}sol;
int x[maxn],y[maxn];
int main() {
int n=read(),s=n*+,t=n*+,S=s+;sol.init(*n+);
sol.AddEdge(S,s,,);
rep(i,,n) x[i]=read(),y[i]=read(),sol.AddEdge(i,i+n,,-),sol.AddEdge(s,i,,),sol.AddEdge(i+n,t,,);
rep(i,,n) rep(j,,n) if(i!=j&&x[i]<=x[j]&&y[i]<=y[j]) sol.AddEdge(i+n,j,,);
printf("%d\n",-sol.solve(S,t));
return ;
}
| 雷神领域 |
| 难度级别：C； 运行时间限制：1000ms； 运行空间限制：262144KB； 代码长度限制：2000000B |
试题描述 |
Lwins_7k+ (GYZ)，Synophia大陆首屈一指的天才魔法师，创造了一个新魔法：雷神领域。 这个魔法会首先在地面上形成正方网格魔法阵列，然后在某些位置召唤雷电轴标。注意：一个位置只能有一个雷电轴标存在。雷电轴标总出现在正方网格魔法阵列的顶点处，所以我们可以用一个有序整数对(x_i,y_i)标记它的位置。 然后，如果存在三个雷电轴标A,B,C满足：x_A=x_B, y_A=y_C，则该魔法会立即召唤一个位置在(x_C,y_B)的雷电轴标，如此往复直至不存在满足条件的雷电轴标组为止。 最后，Lwins_7k+将选择一条正方网格魔法阵列上的路径并使用自然力激活它们，这时候雷神领域的魔法强度就被定义为路径上的雷电轴标所占用的行数/列数中的较小值。但是由于Lwins_7k+才刚创造这个魔法，如果选择的路径中出现U形或往返子路径，那么会给施展魔法的魔法师带来一定危险性。所以选择的路径不应该包含U形子路径或往返子路径。（类似 |__ __ __| 这样的广义U形路径也不行） 由于自然力必须从魔法师的体内调和，所以路径的起点应该是魔法师所站的位置，即正方网格魔法阵列的左下角(0,0)点。 现在他想要询问你——以扫地为生来隐藏自己真实身份的大陆有史以来最伟大的式神制造师Lwins_***，他所能释放的雷神领域的最高魔法强度。当然，路径由你来为他选择。虽然如此，作为一个魔法天才，其实他只关心最高魔法强度而已。 |
输入 |
输入文件field.in第一行包含一个正整数N，表示接下来的数据个数。 接下来N行，每行包含两个正整数x_i,y_i，表示(x_i,y_i)处存在一个雷电轴标。 |
输出 |
输出文件field.out仅包含一行，为可能的最高魔法强度。 |
输入示例 |
7 1 1 1 1 1 1 1 2 1 3 2 2 3 1 |
输出示例 |
3 |
其他说明 |
对于30%的数据：N<=10, 0<x_i,y_i<=5。 对于80%的数据：0<x_i,y_i<=2000。 对于100%的数据：N<=15000, 0<x_i,y_i<=5000。 |
首先明确雷电轴标是有传递性的，我们可以建一个并查集维护横纵坐标的连通性，而如果横坐标x和纵坐标y连通，那么在(x,y)就有一个雷电轴标。
然后5000*5000的DP即可。
#include<cstdio>
#include<cctype>
#include<queue>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i!=-1;i=next[i])
using namespace std;
inline int read() {
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
int pa[maxn*+],f[maxn+][maxn+];
inline int findset(int x) {return pa[x]==x?x:pa[x]=findset(pa[x]);}
int main() {
int n=read();
rep(i,,) pa[i]=i;
rep(i,,n) {
int x=read(),y=read();
pa[findset(x)]=findset(y+maxn);
}
rep(i,,maxn) rep(j,,maxn)
if(findset(i)==findset(j+maxn)) f[i][j]=f[i-][j-]+;
else f[i][j]=max(f[i][j-],f[i-][j]);
printf("%d\n",f[maxn][maxn]);
return ;
}
| 魔术球问题弱化版 |
| 难度级别：C； 运行时间限制：3000ms； 运行空间限制：262144KB； 代码长度限制：2000000B |
试题描述 |
假设有 n 根柱子，现要按下述规则在这 n 根柱子中依次放入编号为 1，2，3，…的球。 （1）每次只能在某根柱子的最上面放球。 （2）在同一根柱子中，任何 2 个相邻球的编号之和为完全平方数。 试设计一个算法，计算出在 n 根柱子上最多能放多少个球。例如，在 4 根柱子上最多可放 11 个球。 对于给定的 n，计算在 n 根柱子上最多能放多少个球。 |
输入 |
第 1 行有 1 个正整数 n，表示柱子数。 |
输出 |
一行表示可以放的最大球数。 |
输入示例 |
4 |
输出示例 |
11 |
其他说明 |
N<=60，时限为3s；比起原题还有弱化在不用打出方案，方案太坑了 |
先二分答案，将i号球看成一个点，如果i<j且i+j是个完全平方数，那么i->j连一条有向边，每一条路径上的球可以放在一根柱子上。问题转化成DAG最小路径覆盖，判断答案是否<=n即可。
#include<cstdio>
#include<cctype>
#include<queue>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i!=-1;i=next[i])
using namespace std;
inline int read() {
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
const int maxm=;
struct Dinic {
int n,m,s,t,clo,d[maxn],vis[maxn],cur[maxn];
int first[maxn],next[maxm];
struct Edge {int from,to,flow;}edges[maxm];
void init(int n) {
this->n=n;m=;
memset(first,-,sizeof(first));
}
void AddEdge(int u,int v,int cap) {
edges[m]=(Edge){u,v,cap};next[m]=first[u];first[u]=m++;
edges[m]=(Edge){v,u,};next[m]=first[v];first[v]=m++;
}
int DFS(int x,int a) {
if(x==t||!a) return a;
int flow=,f;
for(int& i=cur[x];i!=-;i=next[i]) {
Edge& e=edges[i];
if(d[e.to]==d[x]+&&(f=DFS(e.to,min(a,e.flow)))) {
e.flow-=f;edges[i^].flow+=f;
flow+=f;a-=f;if(!a) break;
}
}
return flow;
}
int BFS() {
queue<int> Q;Q.push(s);vis[s]=++clo;
while(!Q.empty()) {
int x=Q.front();Q.pop();cur[x]=first[x];
ren {
Edge& e=edges[i];
if(e.flow&&vis[e.to]!=clo) {
vis[e.to]=clo;
d[e.to]=d[x]+;
Q.push(e.to);
}
}
}
return vis[t]==clo;
}
int solve(int s,int t) {
this->s=s;this->t=t;int flow=;
while(BFS()) flow+=DFS(s,1e9);
return flow;
}
}sol;
int m;
int is(int x) {
int c=(int)sqrt(x)+0.5;
return c*c==x;
}
int check(int n) {
int s=n*+,t=n*+;sol.init(n*+);
rep(i,,n) rep(j,i+,n) if(is(i+j)) sol.AddEdge(i,j+n,);
rep(i,,n) sol.AddEdge(s,i,),sol.AddEdge(i+n,t,);
return sol.solve(s,t)+m>=n;
}
int main() {
m=read();
int l=,r=;
while(l+<r) {
int mid=l+r>>;
if(check(mid)) l=mid;
else r=mid;
}
printf("%d\n",l);
return ;
}
| 征兵 |
| 难度级别：C； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
试题描述 |
一个国王，他拥有一个国家。最近他因为国库里钱太多了，闲着蛋疼要征集一只部队要保卫国家。他选定了N个女兵和M个男兵，但事实上每征集一个兵他就要花10000RMB，即使国库里钱再多也伤不起啊。他发现，某男兵和某女兵之间有某种关系（往正常方面想，一共R种关系），这种关系可以使KING少花一些钱就可以征集到兵，不过国王也知道，在征兵的时候，每一个兵只能使用一种关系来少花钱。这时国王向你求助，问他最少要花多少的钱。 |
输入 |
第一行：T，一共T组数据。 接下来T组数据， 第一行包括N,M,R 接下来的R行 包括Xi,Yi,Vi 表示如果招了第Xi个女兵，再招第Yi个男兵能省Vi元（同样表示如果招了第Yi个男兵，再招第Xi个女兵能也省Vi元） |
输出 |
共T行，表示每组数据的最终花费是多少（因为国库里的钱只有2^31-1，所以保证最终花费在maxlongint范围内） |
输入示例 |
2 5 5 8 5 5 10 |
输出示例 |
71071 54223 |
其他说明 |
数据保证T<=5 ,m,n<=10000,r<=50000,Xi<=m,Yi<=n,Vi<=10000,结果<=2^31-1 |
《挑战程序设计竞赛》有详细解答。
#include<cstdio>
#include<cctype>
#include<queue>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i!=-1;i=next[i])
using namespace std;
inline int read() {
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
const int maxm=;
struct Edge {
int u,v,w;
bool operator < (const Edge& ths) const {
return w>ths.w;
}
}e[maxm];
int pa[maxn];
int findset(int x) {return x==pa[x]?x:pa[x]=findset(pa[x]);}
int main() {
int T=read();
while(T--) {
int n=read(),m=read(),r=read(),ans=;
rep(i,,n+m) pa[i]=i;
rep(i,,r) e[i].u=read()+,e[i].v=read()+n+,e[i].w=read();
sort(e+,e+r+);
rep(i,,r) {
int x=findset(e[i].u),y=findset(e[i].v);
if(x!=y) ans+=e[i].w,pa[x]=y;
}
printf("%d\n",(n+m)*-ans);
}
return ;
}
| 无线通讯网 |
| 难度级别：C； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
试题描述 |
国防部计划用无线网络连接若干个边防哨所。2种不同的通讯技术用来搭建无线网络；每个边防哨所都要配备无线电收发器；有一些哨所还可以增配卫星电话。 任意两个配备了一条卫星电话线路的哨所（两边都拥有卫星电话）均可以通话，无论他们相距多远。而只通过无线电收发器通话的哨所之间的距离不能超过D，这是受收发器的功率限制。收发器的功率越高，通话距离D会更远，但同时价格也会更贵。 收发器需要统一购买和安装，所以全部哨所只能选择安装一种型号的收发器。换句话说，每一对哨所之间的通话距离都是同一个D。 你的任务是确定收发器必须的最小通话距离D，使得每一对哨所之间至少有一条通话路径（直接的或者间接的）。 |
输入 |
第1行：2个整数S（1<=S<=100）和P（S<P<=500），S表示可安装的卫星电话的哨所数，P表示边防哨所的数量。 接下里P行，每行描述一个哨所的平面坐标（x,y），以km为单位，整数，0<=x,y<=10000。 |
输出 |
第1行：1个实数D，表示无线电收发器的最小传输距离。精确到小数点后两位。 |
输入示例 |
2 4 0 100 0 300 0 600 150 750 |
输出示例 |
212.13 |
其他说明 |
对于20%的数据 P=2，S=1 对于另外20%的数据 P=4，S=2 对于100%的数据 1<=S<=100，S<P<=500 |
二分答案，用并查集判判即可。
#include<cstdio>
#include<cctype>
#include<queue>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i!=-1;i=next[i])
using namespace std;
inline int read() {
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
int n,m,cnt,x[maxn],y[maxn];
struct Edge {
int u,v,w;
}e[maxn*maxn>>];
int pa[maxn];
int findset(int x) {return x==pa[x]?x:pa[x]=findset(pa[x]);}
int check(int x) {
rep(i,,n) pa[i]=i;
rep(i,,cnt) if(e[i].w<=x) pa[findset(e[i].u)]=findset(e[i].v);
int res=;
rep(i,,n) if(i==findset(i)) res++;
return res==||res<=m;
}
int main() {
m=read();n=read();
rep(i,,n) x[i]=read(),y[i]=read();
rep(i,,n) rep(j,i+,n) e[++cnt]=(Edge){i,j,(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])};
int l=,r=,mid;
while(l<r) if(check(mid=l+r>>)) r=mid; else l=mid+;
printf("%.2lf\n",sqrt(l));
return ;
}