[CLYZ2017]day12
跳马
Description
有一张无穷大,没有边界的棋盘,你要将马从\((0,0)\)移动到\((x,y)\).
每一步你可以使马的横坐标,纵坐标其中一个\(\pm1\),另一个\(\pm2\).
你需要求出最少步数.有\(t\)组数据.
Input
第一行一个正整数\(t\),接下来\(t\)行每行两个整数\(x,y\).
Output
\(t\)行,每行一个整数表示答案.
Sample Input
8
1 2
2 1
1 -2
2 -1
-1 2
-2 -1
-2 1
-1 -2Sample Output
1 1 1 1 1 1 1 1HINT
\(1\leq{t}\leq1000,|x|,|y|\leq10^9\).
Solution
100分
打表找个规律.(虽然是可以证明的).
- 表
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define M 8
#define N 1001
using namespace std;
typedef long long ll;
int x[M]={-2,-2,-1,-1,1,1,2,2};
int y[M]={1,-1,2,-2,2,-2,1,-1};
int a[N][N];
queue qx,qy;
inline int read(){
int ret=0;char c=getchar();
while(!isdigit(c))
c=getchar();
while(isdigit(c)){
ret=(ret<<1)+(ret<<3)+c-'0';
c=getchar();
}
return ret;
}
inline void bfs(int u,int v){
a[u][v]=1;
qx.push(u);qy.push(v);
while(!qx.empty()){
u=qx.front();qx.pop();
v=qy.front();qy.pop();
for(int i=0,j,k;i=0&&j=0&&k - code
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int x,y,t;
inline void Aireen(){
scanf("%d",&t);
while(t--){
scanf("%d%d",&x,&y);
x=abs(x);y=abs(y);
if(x>y) swap(x,y);
if(!x){
if(!y) puts("0");
else if(y==1) puts("3");
else if(y==2) puts("2");
else if(y==3) puts("3");
else printf("%d\n",y/4*2+y%4);
}
else if(y>=(x<<1)){
y-=(x<<1);
printf("%d\n",x+y/4*2+y%4);
}
else if(x>=4){
y-=x;x-=4;
if(!(x%3)){
if(!y) printf("%d\n",(2+x/3)*2);
else printf("%d\n",(2+x/3)*2-1+(y-1)/3+(y-1)%3);
}
else if(x%3==1){
if(!y) printf("%d\n",(2+x/3)*2);
else if(y==1) printf("%d\n",(2+x/3)*2+1);
else printf("%d\n",(2+x/3)*2+(y-2)/3+(y-2)%3);
}
else printf("%d\n",(2+x/3)*2+y/3+y%3);
}
else{
if(x==1) puts("2");
else if(x==2) printf("%d\n",6-y);
else if(x==3) printf("%d\n",y-1);
}
}
}
int main(){
freopen("jump.in","r",stdin);
freopen("jump.out","w",stdout);
Aireen();
fclose(stdin);
fclose(stdout);
return 0;
} 绝对值
Description
有\(n\)个实数\(x_i\),其中\(x_i\)在\([l_i,r_i]\)中均匀随机.
你需要求出\(|\sum{x_i}|\)的期望.答案对\(998244353\)取模.
Input
第一行一个正整数\(n\).接下来\(n\)行每行两个整数\(l_i,r_i\).
Output
一行一个整数表示答案.
Sample Input
2
-2 3
-2 1Sample Output
199648872HINT
\(-10^6\leq{l_i}\leq{r_i}\leq{10^6}\).
Solution
100分
我不会...先贴份闫神的题解...
设\(f(i,x)\)表示|前\(i\)个变量的和-\(x\)|的期望.
显然这是一个分段多项式函数,每一段可以通过对\(f(i-1)\)积分得到.
\(f(i)\)的段点为\(f(i-1)\)的段点减去\(l_i\)或加上\(r_i\).
时间复杂度\(O(\sum(2^i\times{i^2}))=O(2^n\times{n^2})\).
序列
Description
给定正整数\(m\)以及长度为\(n\)的序列对\((a_i,b_i)\),你需要将它分为若干段,满足以下\(2\)个条件:
- 若\(i
- 每一段的\(a\)的最大值之和\(\leq{m}\).
在此基础上,你需要最小化每一段的\(b\)的和的最大值.
Input
第一行两个正整数\(n,m\),接下来\(n\)行每行两个正整数\(a_i,b_i\).
Output
一行一个整数表示答案.
Sample Input
4 6
4 3
3 5
2 5
2 4Sample Output
9HINT
\(n\leq100000,m\leq10^{12},1\leq{a_i,b_i}\leq2\times10^9\).
Solution
100分
条件一等价于若\(i
合并这样的段.
二分每一段的\(b\)的和的最大值\(mx\).
最小化每一段的\(a\)的最大值之和.
\(f[i]\)表示前\(i\)个数的\(a\)的最大值之和的最小值.
\(f[i]=min\{f[j]+mx[j+1][i]\}\).
用\(set\)维护一个\(a\)的下降序列,每次把\(set\)不合法的\(a_i\)弹出.
显然会影响当前决策的是满足\(s[i]-s[j]\leq{mx}\)最小的\(j\),以及\(set\)中的最小值.
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define N 100005
#define max(a,b) a>b?a:b
#define min(a,b) a s;
inline bool chk(ll k){
ll sum=0ll;int l=0;h=1;t=0;
for(int i=1;i<=n;++i){
while(h<=t&&a[i]>=a[q[t]]){
if(hk) sum-=b[++l];
while(h<=t&&l>=q[h]){
if(h>1;
if(chk(mid)) r=mid;
else l=mid+1;
}
printf("%lld\n",l);
}
int main(){
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
Aireen();
fclose(stdin);
fclose(stdout);
return 0;
}