10.28模拟赛
幸运数字(number)
Description
LYK 最近运气很差，例如在 NOIP 初赛中仅仅考了 90 分，刚刚卡进复赛，于是它决定使 用一些方法来增加自己的运气值。
它觉得，通过收集幸运数字可以快速的增加它的 RP 值。
它给幸运数字下了一个定义：如果一个数 x 能被 3 整除或被 5 整除或被 7 整除，则这个 数为幸运数字。
于是它想让你帮帮它在 L~R 中存在多少幸运数字
Input
第一行两个数 L,R。
Output
一个数表示答案 。
数据范围
对于 50%的数据 1<=L<=R<=10^5。
对于 60%的数据 1<=L<=R<=10^9。
对于 80%的数据 1<=L<=R<=10^18。
对于 90%的数据 1<=L<=R<=10^100。
对于另外 10%的数据 L=1， 1<=R<=10^100。
对于 100%的数据 L， R 没有前导 0。
哇,水题.
很明显是容斥原理.
\(L\)到\(R\)的答案可以化简为\(1\)到\(R\)的答案减去\(1\)到\(L-1\)的答案.(貌似这也是容斥)
所以根据容斥原理的式子(这里就不放了)。
最终推得式子为
\[
A=\frac{R}{3}+\frac{R}{5}+\frac{R}{7}-\frac{R}{15}-\frac{R}{21}-\frac{R}{35}+\frac{R}{105}
\]
\[
B=\frac{L-1}{3}+\frac{L-1}{5}+\frac{L-1}{7}-\frac{L-1}{15}-\frac{L-1}{21}-\frac{L-1}{35}+\frac{L-1}{105}
\]
\[
ans=A-B
\]
但是看到数据范围你不慌嘛?
高精？完了要凉
硬着头皮码(tiao)了1个半小时.
问题不大.
代码
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define clear(a) memset(a,0,sizeof a)
#define N 10008
#define R register
using namespace std;
int len,a[N],b[N],t[N],ans[N];
int sa[N],sb[N],c[2]={1,1};
char l[N],r[N];
inline void pre(int *a,int *b)
{
clear(sa);clear(sb);
sa[0]=a[0];
for(int i=1;i<=a[0];i++)
sa[i]=a[a[0]-i+1];
for(int i=1;i<=b[0];i++)
sb[i]=b[b[0]-i+1];
for(R int i=1;i<=sa[0];i++)
{
sa[i]-=sb[i];
if(sa[i]<0)
{
sa[i]+=10;
sa[i+1]--;
}
}
while(sa[0]>1 and sa[a[0]]==0)sa[0]--;
a[0]=sa[0];
for(int i=1;i<=sa[0];i++)a[i]=sa[sa[0]-i+1];
}
inline void div(int *a,int *b,int x)
{
int plus=0;
a[0]=b[0];
for(R int i=1;i<=b[0];i++)
{
plus=plus*10+b[i];
a[i]=plus/x;plus%=x;
}
}
inline void add(int *a,int *b)
{
clear(sa),clear(sb);
int len1=a[0],len2=b[0],len=1;
for(R int i=1;i<=len2;i++)
sb[i]=b[len2-i+1];
for(;len<=len1 or len<=len2;len++)
{
sa[len]+=a[len]+sb[len];
sa[len+1]=sa[len]/10;
sa[len]=sa[len]%10;
}
while(len>1 and sa[len]==0)len--;
sa[0]=len;
for(R int i=0;i<=sa[0];i++)a[i]=sa[i];
}
inline void jian(int *a,int *b)
{
clear(sb);
for(R int i=1;i<=b[0];i++)
sb[i]=b[b[0]-i+1];
for(R int i=1;i<=a[0];i++)
{
a[i]=a[i]-sb[i];
if(a[i]<0)
{
a[i]=a[i]+10;
a[i+1]--;
}
}
while(a[0]>1 and a[a[0]]==0)a[0]--;
}
int main()
{
freopen("number.in","r",stdin);
freopen("number.out","w",stdout);
scanf("%s",l);
scanf("%s",r);
int len1=strlen(l),len2=strlen(r);
a[0]=len1,b[0]=len2;
for(int i=1;i<=len1;i++) a[i]=l[i-1]-'0';
for(int i=1;i<=len2;i++) b[i]=r[i-1]-'0';
pre(a,c);
/**/
div(t,b,3);add(ans,t);
div(t,b,5);add(ans,t);
div(t,b,7);add(ans,t);
div(t,a,3);jian(ans,t);
div(t,a,5);jian(ans,t);
div(t,a,7);jian(ans,t);
/**/
/**/
div(t,a,15);add(ans,t);
div(t,a,21);add(ans,t);
div(t,a,35);add(ans,t);
div(t,b,15);jian(ans,t);
div(t,b,21);jian(ans,t);
div(t,b,35);jian(ans,t);
/**/
/**/
div(t,b,105);add(ans,t);
div(t,a,105);jian(ans,t);
/**/
for(R int i=ans[0];i>=1;i--)
printf("%d",ans[i]);
fclose(stdin);
fclose(stdout);
return 0;
}位运算(bit)
Description
lyk 最近在研究位运算。它发现除了 xor,or,and 外还有很多运算。
它新定义了一种运算符“#” 。 具体地，可以由 4 个参数来表示。 令 a[i][j]表示 i#j。 其中 i,j 与 a 的值均∈[0,1]。
当然问题可以扩展为>1 的情况，具体地，可以将两个数分解为 p 位，然后对于每一位 执行上述的位运算，再将这个二进制串转化为十进制就可以了。
例如当 a[0][0]=0， a[1][1]=0， a[0][1]=1， a[1][0]=1 时,3#4 在 p=3 时等于 7,2#3 在 p=4 时等于 1（实际上就是异或运算）。
现在 lyk 想知道的是，已知一个长为 n 的数列 b。它任意选取一个序列 c，满 足 c1<c2<…<ck，其中 1≤c1 且 ck≤n，定义这个序列的价值为 b{c1}#b{c2}#…#b{ck} 的平方。
这里我们假设 k 是正整数，因此满足条件的 c 的序列个数一定是 2^n-1 。
lyk 想知道 所有满足条件的序列的价值总和是多少。
由于答案可能很大， 你只需输出答案对 1,000,000,007 取模后的结果即可
Input
第一行两个数 n,p。
第二行 4 个数表示 \(a[0][0]， a[0][1]， a[1][0]， a[1][1]\)。
第三行 n 个数表示 bi(0<=bi<2^p)。
Output
一个数表示答案 。
数据范围
总共 10 组数据。
对于第 1,2 组数据 n<=5。
对于第 3,4 组数据 n<=10000， p=1。
对于第 5 组数据 a 值均为 0。
对于第 6 组数据 a 值均为 1。
对于第 7 组数据 \(a[0][0]=0,a[1][0]=0,a[1][1]=1,a[0][1]=1\)。
对于第 8,9 组数据 n<=1000， p<=10。
对于所有数据 n<=10000， 1<=p<=30。
对于现在的我来说不可做不可做。
连特判都错了
\(std\)
将一个数的平方拆成若干幂次的平方，例如\(7^{2}=(1+2+4)^2\)。
观察答案的形式为\(1*1+1*2+1*4+2*1+2*2+2*4+4*1+4*2+4*4\)。
枚举每两位，令\(dp[i][j][k]\)表示到第i位，此时第一位为j，第二位为k的方案总数，累加即可。
蚂蚁运输(ant)
LYK 在观察一些蚂蚁。
蚂蚁想要积攒一些货物来过冬。
积攒货物的方法是这样的。 对于第 i 只蚂蚁，它要从 li出发，拿起货物，走到 ri处放下货物，需要消耗的时间为|ri-li|。 而且所有蚂蚁都是可以同时进行的，也就是说，假如有 m 只蚂蚁，那么运输完货物的时间 为 max{|ri-li|}。
LYK 决定帮蚂蚁一把，它发明了空间传输装置。具体地，当蚂蚁走到 X 处时，它可以不 耗费任意时间的情况下瞬间到达 Y，或者从 Y 到达 X。也就是说，一个蚂蚁如果使用了空间 传输装置，它耗费的时间将会是 min{|li-X|+|ri-Y|,|li-Y|+|ri-X|}，当然蚂蚁也可以选择徒步走 到目标点。
由于空间传输装置非常昂贵， LYK 打算只建造这么一台机器。并且 LYK 想让蚂蚁运输完 货物的时间尽可能短，你能帮帮它吗？
Input
第一行两个数 n,m， n 表示 li,ri 的最大值。
接下来 m 行，每行两个数 li,ri。
Output
一个数表示答案 。
数据范围
对于 20%的数据 n,m<=100。
对于 40%的数据 n,m<=1000。
对于 60%的数据 n<=100000， m<=1000。
对于 80%的数据 n,m<=100000
对于 100%的数据 n,m<=1000000， 1<=li,ri<=n（li=ri 时你甚至可以无视这只蚂蚁）。
这套题太恶心了!
尤其是这题.
出题人造数据竟然不说\(l\)可能大于\(r\)！其实是我没看到中间的逗号
然后由\(100pts\)变成了\(30pts\)！！！
要不\(rank3\)了!
二分答案
读入时一定要！一定要！保证\(l_i<=r_i\)
\(ok(mid)\)时
设建的传送站为\(X Y\)
\(abs(l-X)+abs(r-Y)<=mid\)
将\(abs\)拆开,存在四种情况
- \(l-X+r-Y<=mid\)
- \(l-X+Y-r<=mid\)
- \(X-l+r-Y<=mid\)
- \(X-l+Y-r<=mid\)
则存在以下俩不等式.
\(l+r-mid<=X+Y<=l+r+mid\)
\(l-r-mid<=X-Y<=l-r+mid\)
只要存在X,Y对于所有的l,r满足上面两条件即可
然后逼近即可.
一定要判断输入!!!!!!
\(std\)
观察到答案具有可二分性。我们可以二分答案。
由于路径都是无向的，因此对于任意一条方案li,ri若li>ri则可以交换li和ri。
我们设二分的答案为x。
对于那些li+x>=ri的方案我们直接默认为可行。
我们规定X<=Y。
对于li+x<ri的方案。只有一种可能能够完成，即，从li出发，到达X，到达Y，到达ri。
也就是说，如果X确定，Y存在于一段区间内。
我们来看li>=X的情况。
先求出X=n时符合条件的Y的区间。当X慢慢减少时，这个区间肯定也在慢慢合拢，并且满足li>=X的条件也会越来越多。我们可以线性求出所有这个区间。
对于li<X的情况也同理。
这样就能做到线性判断，总复杂度nlgn。（这里默认n与m同阶）
代码
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<ctime>
#include<algorithm>
#define R register
using namespace std;
inline void in(int &x)
{
int f=1;x=0;char s=getchar();
while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}
while(isdigit(s)){x=x*10+s-'0';s=getchar();}
x*=f;
}
int n,m,cnt;
struct cod{int l,r;}ant[1000008];
inline bool ok(int x)
{
R int le=-2147483644,ri=2147483644;
for(R int i=1;i<=cnt;i++)
{
if(ant[i].r-ant[i].l<=x)continue;
le=max(le,ant[i].l+ant[i].r-x);
ri=min(ri,ant[i].l+ant[i].r+x);
}
if(le>ri)return false;
le=-2147483644,ri=2147483644;
for(R int i=1;i<=cnt;i++)
{
if(ant[i].r-ant[i].l<=x)continue;
le=max(le,ant[i].l-ant[i].r-x);
ri=min(ri,ant[i].l-ant[i].r+x);
}
if(le>ri)return false;
return true;
}
int main()
{
freopen("ant.in","r",stdin);
freopen("ant.out","w",stdout);
in(n),in(m);
{
for(R int i=1,x,y;i<=m;i++)
{
in(x),in(y);
if(x>y)swap(x,y);
ant[++cnt].l=x,ant[cnt].r=y;
}
int l=0,r=1e9,ans;
while(l<=r)
{
int mid=(l+r)>>1;
if(ok(mid))r=mid-1,ans=mid;
else l=mid+1;
}
printf("%d",ans);
}
fclose(stdin);
fclose(stdout);
return 0;
}