济南-1101试题解题报告
By shenben
本解题报告解析均为100分解题思路。
题意自行读题。（总结题意太累了……）
上午
T1 sequence
解析：将a进行排序后，枚举所有位置，若ai<=a{i-1},则答案加上a{i-1}-ai+1，并将ai变成a{i-1}+1即可。
T2 lab
解析：令dp[i][j]表示按过i次，当前停留在j层，考虑哪些层可以到达i层，这肯定是连续的，利用（前缀和+（滚动数组 或 降维））优化可以做到nk。
T3 travel
解析：对于每个点求出最短路树，这棵树一定有n-1条边，对于每条边被炸毁，若在最短路树上，则重新求一次最短路，否则直接统计答案。最短路可以用BFS代替。因此总复杂度为n^2m。
当n=m时，一条边炸毁后图要么不连通，要么是一棵树，这棵树是很有特点的，可以用容斥原理计算出答案。
下午
T1 number
解析：L~R的答案可以化简为1~R的答案减去1~L-1的答案。
根据容斥原理，1~R的答案为R/3+R/5+R/7-R/21-R/15-R/35+R/210。L同理。套上高精度即可。
T2 bit
解析：将一个数的平方拆成若干幂次的平方，例如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的方案总数，累加即可。
T3 ant
解析：观察到答案具有可二分性。我们可以二分答案。
由于路径都是无向的，因此对于任意一条方案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同阶）
上午
T1代码：
#include<cstdio> #include<iostream> #include<algorithm> using namespace std; const int N=1e6+10; int n,a[N]; long long ans; #define name "sequence" int main(){ freopen(name".in","r",stdin); freopen(name".out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",a+i); sort(a+1,a+n+1); for(int i=2;i<=n;i++){ if(a[i]<=a[i-1]){ ans+=a[i-1]+1-a[i]; a[i]=a[i-1]+1; } } cout<<ans; fclose(stdin); fclose(stdout); return 0; }
T2代码：
#include<cstdio> #define ll long long using namespace std; const int N=1e5+10; const ll mod=1e9+7; int n,a,b,k; ll ans,dp[N],sum[N]; #define name "lab" int main(){ freopen(name".in","r",stdin); freopen(name".out","w",stdout); scanf("%d%d%d%d",&n,&a,&b,&k); dp[a]=1; for(int i=a;i<=n;i++) sum[i]=1; for(int i=1;i<=k;i++){ dp[b]=0; for(int j=1;j<b;j++) dp[j]=(sum[(j+b-1)/2]-sum[j]+sum[j-1]+mod)%mod; for(int j=b+1;j<=n;j++) dp[j]=(sum[n]-sum[(j+b)/2]-sum[j]+sum[j-1]+mod)%mod; for(int j=1;j<=n;j++) sum[j]=(sum[j-1]+dp[j])%mod; } for(int i=1;i<=n;i++) ans=(ans+dp[i])%mod; printf("%d",(int)ans); fclose(stdin); fclose(stdout); return 0; } //最后一个点TLE or AC取决于编译器 /* 60分dp代码 丢失了 */
T3代码：
下午
T1代码：
#include<iostream> #include<string> #include<cstring> #include<cstdio> #include<cstdlib> #include<algorithm> #define ll long long #define name "number" using namespace std; string l,r; class bign { private: static const int maxn = 5000; int op[maxn]; int len;//数长 void clean() { while (len > 0 && !op[len])//去除前导0 len--; len++; } void sum(bign &a, const bign &b)//大数减小数，结果在a中 { for (int i = 0; i< a.len; i++) { a.op[i] -= b.op[i]; if (a.op[i]< 0) { a.op[i] += 10; a.op[i + 1]--; } } a.clean(); } public: bign(const string &s) { *this = s; } bign() { memset(op, 0, sizeof(op)); len = 1;//默认为0 } bign(int num) { *this = num; } bign operator = (int num) { char s[20]; sprintf(s, "%d", num); *this = s; return *this; } bign operator = (const string &s) { memset(op, 0, sizeof(op)); len = s.length(); for (int i = 0, j = len - 1; j >= 0; j--, i++) op[i] = s[j] - '0'; clean(); return *this; } bign operator + (const bign &b) { bign c = *this; int i; c.len = max(c.len, b.len);//取长度高的 for (i = 0; i< c.len; i++)//对应位相加 { c.op[i] += b.op[i]; if (c.op[i] > 9)//处理进位 { c.op[i + 1]++; c.op[i] -= 10; } } c.clean(); return c; } bign operator - (const bign &b) { if (*this< b) { bign c = b; sum(c, *this); return -c; } bign c = *this; sum(c, b); c.clean(); return c; } bign operator * (const bign &b)const { int i, j; bign c; for (i = 0; i< this->len; i++) for (j = 0; j< b.len; j++) { c.op[i + j] += this->op[i] * b.op[j]; } c.len = this->len + b.len;//长度最多为两数长度之和 for (i = 0; i< c.len; i++) { c.op[i + 1] += (c.op[i] / 10); c.op[i] %= 10; } c.clean(); return c; } bign operator / (const bign &b)//模拟除法 { int i, j; bign c = *this, a; for (i = c.len - 1; i >= 0; i--) { a = a * 10 + c.op[i]; for (j = 1; j< 10; j++)//a是b的多少倍 if (a< b * j) break; j--; a = a - b * j;//余数 c.op[i] = j;//对应位的倍数 } c.clean(); return c; } bign operator % (const bign &b) { int i, j; bign c = *this, a; for (i = c.len - 1; i >= 0; i--) { a = a * 10 + c.op[i]; for (j = 1; j< 10; j++)//a是b的多少倍 if (a< b * j) break; j--; a = a - b * j;//余数 } return a; } bign operator ^ (int n) { bign c = 1; bign d = *this; while (n) { if (n & 1) c = c * d; d = d * d; n >>= 1; } return c; } bign operator - ()//取反 { bign c = *this; c.op[len - 1] = -c.op[len - 1];//高位取反 return c; } bool operator< (const bign &b) { if (len == b.len) { for (int i = len - 1; i >= 0; i--) { if (op[i] != b.op[i]) return op[i]< b.op[i]; } } return len< b.len; } friend ostream &operator<< (ostream &out, const bign &res) { for (int i = res.len - 1; i >= 0; i--) out<<res.op[i]; //out<<endl; return out; } friend istream &operator >> (istream &in, bign &res) { string s; in>>s; res = s; return in; } string to_str() { string s; for (int i = 0; i< len; i++) s += (op[i] + '0'); return s; } int length() { return len; } }; bign a,b,ans1,ans2; bign cc=0; bign work(bign n){ bign res=0; res=res+(n/3); res=res+(n/5); res=res+(n/7); res=res-(n/15); res=res-(n/21); res=res-(n/35); res=res+(n/105); return res; } int main(){ freopen(name".in","r",stdin); freopen(name".out","w",stdout); cin>>l>>r; a=l;b=r; a=a-1; ans1=work(a); ans2=work(b); cout<<ans2-ans1; return 0; }
T2代码：
#include<cstdio> using namespace std; const int mod=1000000007; int n,k,b[50005],a[2][2],dp[2][2],DP[2][2]; long long ans,sum; #define name "bit" int main(){ freopen(name".in","r",stdin); freopen(name".out","w",stdout); scanf("%d%d",&n,&k); scanf("%d%d%d%d",&a[0][0],&a[0][1],&a[1][0],&a[1][1]); for(int i=1;i<=n;i++) scanf("%d",&b[i]); for(int i=0,X1,Y1,X2,Y2;i<k;i++){ for(int j=i;j<k;j++){ for(X1=0;X1<2;X1++){ for(Y1=0;Y1<2;Y1++){ DP[X1][Y1]=dp[X1][Y1]=0; } } for(int l=1;l<=n;l++){ for(X1=0;X1<2;X1++){ for(Y1=0;Y1<2;Y1++){ if(dp[X1][Y1]){ X2=a[X1][b[l]&(1<<i)?1:0]; Y2=a[Y1][b[l]&(1<<j)?1:0]; DP[X2][Y2]+=dp[X1][Y1]; if(DP[X2][Y2]>=mod) DP[X2][Y2]-=mod; } } } X2=b[l]&(1<<i)?1:0; Y2=b[l]&(1<<j)?1:0; DP[X2][Y2]++; if(DP[X2][Y2]>=mod) DP[X2][Y2]-=mod; for(X1=0;X1<2;X1++){ for(Y1=0;Y1<2;Y1++){ dp[X1][Y1]+=DP[X1][Y1]; if(dp[X1][Y1]>=mod) dp[X1][Y1]-=mod; DP[X1][Y1]=0; } } } sum=(1LL<<i)*(1LL<<j)%mod; if(i!=j) sum<<=1; ans=(ans+sum*dp[1][1])%mod; } } printf("%I64d",ans); fclose(stdin); fclose(stdout); return 0; } /*80分代码存档 #include<cstdio> #include<cstring> #include<iostream> #define N 50005 #define ll long long #define name "bit" #define g(x,t) ((b[x]&(1<<(t)))>>t) using namespace std; const unsigned int mod=1e9+7; unsigned int tra[2][2]; unsigned int dp[2][33][33][2][2]; int n,p,b[N],pw2[N+N]; ll ans=0; int main(){ freopen(name".in","r",stdin); freopen(name".out","w",stdout); int now=0;cin>>n>>p; cin>>tra[0][0]>>tra[0][1]>>tra[1][0]>>tra[1][1]; pw2[0]=1;for(int i=1;i<=n*2;i++) pw2[i]=pw2[i-1]*2%mod; for(int i=1;i<=n;i++) scanf("%d",&b[i]); for(int i=1;i<=n;i++){ memcpy(dp[now^1],dp[now],sizeof(dp[now])); for(int p1=0;p1<p;p1++) for(int p2=0;p2<p;p2++) for(int sta1=0;sta1<=1;sta1++) for(int sta2=0;sta2<=1;sta2++) (dp[now^1][p1][p2][tra[sta1][g(i,p1)]][tra[sta2][g(i,p2)]]+=dp[now][p1][p2][sta1][sta2])%=mod; for(int p1=0;p1<p;p1++) for(int p2=0;p2<p;p2++) dp[now^1][p1][p2][g(i,p1)][g(i,p2)]++; now^=1; } for(int p1=0;p1<p;p1++) for(int p2=0;p2<p;p2++) ans=(ans+dp[now][p1][p2][1][1]*1ll*pw2[p1+p2] )%mod; cout<<ans<<endl; return 0; }*/
T3代码：
#include<cstdio> #include<algorithm> #define name "ant" using namespace std; const int N=1e6+5; const int INF=0x3f3f3f3f; struct node{ int l,r; }p[N]; int n,m; bool judge(int x){ int mn1=INF,mx1=-INF,mn2=INF,mx2=-INF; for(int i=0;i<m;++i){ if(p[i].r-p[i].l<=x)continue; mn1=min(mn1,p[i].l+p[i].r+x); mx1=max(mx1,p[i].l+p[i].r-x); mn2=min(mn2,p[i].r-p[i].l+x); mx2=max(mx2,p[i].r-p[i].l-x); } if(mn1>=mx1&&mn2>=mx2)return true; return false; } int main(){ freopen(name".in","r",stdin); freopen(name".out","w",stdout); scanf("%d%d",&n,&m); for(int i=0;i<m;++i){ scanf("%d%d",&p[i].l,&p[i].r); if(p[i].l>p[i].r)swap(p[i].l,p[i].r); } int l=0,r=n; while(l<r){ int mid=(l+r)>>1; if(judge(mid))r=mid; else l=mid+1; } printf("%d ",(l+r)>>1); return 0; }
上午
完美的序列(sequence)
Time Limit:1000ms
Memory Limit:64MB
题目描述
LYK
认为一个完美的序列要满足这样的条件：对于任意两个位置上的数都不相同。然而
并不是所有的序列都满足这样的条件。
于是 LYK
想将序列上的每一个元素都增加一些数字(当然也可以选择不增加)，使得整个
序列变成美妙的序列。
具体地， LYK 可以花费 1 点代价将第
i 个位置上的数增加 1，现在 LYK 想花费最小的代价
使得将这个序列变成完美的序列。
输入格式(sequence.in)
第一行一个数 n，表示数字个数。
接下来一行 n 个数 ai 表示 LYK
得到的序列。
输出格式(sequence.out)
一个数表示变成完美的序列的最小代价。
输入样例
4
1 1 3 2
输出样例
3
数据范围
对于 30%的数据 n<=5。
对于 60%的数据 n<=1000。
对于 80%的数据 n<=30000，
ai<=3000。
对于 100%的数据 n<=100000，
1<=ai<=100000。
LYK 与实验室(lab)
Time Limit:5000ms
Memory Limit:64MB
题目描述
LYK 在一幢大楼里，这幢大楼共有 n 层，
LYK 初始时在第 a 层上。
这幢大楼有一个秘密实验室，在第 b
层，这个实验室非常特别，对 LYK 具有约束作用，
即若 LYK 当前处于 x
层，当它下一步想到达 y 层时，必须满足|x-y|<|x-b|，而且由于实验室
是不对外开放的，电梯无法停留在第 b 层。
LYK 想做一次旅行，即它想按 k
次电梯，它想知道不同的旅行方案个数有多少个。
两个旅行方案不同当前仅当存在某一次按下电梯后停留的楼层不同。
输入格式(lab.in)
一行 4 个数， n,a,b,k。
输出格式(lab.out)
一个数表示答案，由于答案较大，将答案对
1000000007 取模后输出。
输入样例 1
5 2 4 1
输出样例 1
2
输入样例 2
5 2 4 2
输出样例 2
2
输入样例 3
5 3 4 1
输出样例 3
0
数据范围
对于 20%的数据 n,k<=5。
对于 40%的数据 n,k<=10。
对于 60%的数据 n,k<=500。
对于 90%的数据 n,k<=2000。
对于 100%的数据 n,k<=5000。
旅行(travel)
Time Limit:1000ms
Memory Limit:64MB
题目描述
LYK 想去一个国家旅行。这个国家共有 n
个城市，有些城市之间存在道路，我们假定这
些道路长度都是 1 的，更准确的说，共有 m
条道路。
我们定义城市 A 与城市 B 的最短路为 A
到 B 的所有路径中，经过的道路最少的那条道
路。最短路的长度为这条道路的所有道路长度之和，由于所有道路长度都为 1，因此假如 A
到 B 之间最短路的道路条数为 k，则 A
到 B 的最短路长度为 k。
我们定义整个国家的最短路为任意两个城市（
A,B 与 B,A 算作不同的点对）之间的最短
路长度的和。
然而这个国家正处于危乱之中，极有可能一条道路会被恐怖分子炸毁。
LYK
想知道，万一某条道路被炸毁了，整个国家的最短路为多少。若炸毁这条道路后整
个国家不连通了，那么就输出“ INF”
(不加引号)。
输入格式(travel.in)
第一行两个数 n,m。
接下来 m 行，每行两个数
u,v，表示存在一条道路连接 u,v(数据保证不存在自环)。
输出格式(travel.out)
输出 m 行，第 i 行的值表示当第 i
条道路被炸毁时，整个国家的最短路是多少，若图不
连通，则输出“ INF”。
输入样例
2 2
1 2
1 2
输出样例
2 2
数据范围
对于 20%的数据
n<=10,n<m<=100。
对于 40%的数据 1<=n<m<=100。
对于 70%的数据
1<=n<=100,n<m<=3000。
对于再另外 10%的数据对于所有节点（ i
1<=i<n），存在一条边连接 i与 i+1，且 n=m，n<=100。
对于再再另外 10%的数据对于所有节点 i（
1<=i<n），存在一条边连接 i 与 i+1，且 n=m，
n<=1000。
对于再再再另外 10%的数据对于所有节点（
i 1<=i<n），存在一条边连接 i 与 i+1，且 n=m，
n<=100000。
下午
幸运数字(number)
Time Limit:1000ms
Memory Limit:64MB
题目描述
LYK 最近运气很差，例如在 NOIP
初赛中仅仅考了 90 分，刚刚卡进复赛，于是它决定使
用一些方法来增加自己的运气值。
它觉得，通过收集幸运数字可以快速的增加它的
RP 值。
它给幸运数字下了一个定义：如果一个数 x
能被 3 整除或被 5 整除或被 7 整除，则这个
数为幸运数字。
于是它想让你帮帮它在 L~R
中存在多少幸运数字。
输入格式(number.in)
第一行两个数 L,R。
输出格式(number.out)
一个数表示答案。
输入样例
10 15
输出样例
4
数据范围
对于 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。
位运算(bit)
Time Limit:2000ms
Memory Limit:64MB
题目描述
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 取模后的结果即可。
输入格式(bit.in)
第一行两个数 n,p。
第二行 4 个数表示 a[0][0]，
a[0][1]， a[1][0]， a[1][1]。
第三行 n 个数表示
bi(0<=bi<2^p)。
输出格式(bit.out)
一个数表示答案。
输入样例
3 30
0 1 1 0
1 2 3
输出样例
28
样例解释
{1}的价值为 1， {2}的价值为 4，
{3}的价值为 9， {1,2}的价值为 9， {1,3}的价值为 4， {2,3}
的价值为 1， {1,2,3}的价值为
0，因此 7 个子集的价值总和为 28。
数据范围
总共 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。
蚂蚁运输(ant)
Time Limit:5000ms
Memory Limit:64MB
题目描述
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 想让蚂蚁运输完
货物的时间尽可能短，你能帮帮它吗？
输入格式(ant.in)
第一行两个数 n,m， n 表示 li,ri
的最大值。
接下来 m 行，每行两个数 li,ri。
输出格式(ant.out)
一个数表示答案
输入样例
5 2
1 3
2 4
输出样例
1
数据范围
对于 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 时你甚至可以无视这只蚂蚁）。
样例解释
令空间传输装置的参数中 X=2， Y=3
或者 X=3， Y=2 都行。