第一次月赛 本来想着拿个好名次 结果倒数第一 如此真实 哈哈我太菜了（暴风哭泣
结束后照着题解边抄边补了
A: 收集云彩(二)
时间限制: 1 Sec 内存限制: 2048 MB
提交: 63 解决: 7
[提交][状态][讨论版][命题人:201607255]
题目描述
许小铭看到陈小青收集云彩也跟着一起来收集云彩，他希望收集理工大学上方的云彩送给新同学，一共有 n 个云彩从理工大上方飘过，给出每个时刻下云彩的形状，用不同的整数表示不同的形状。在收集的过程中，陈小青不希望有重复的云彩。你可以从任意 a 时刻开始，当有重复云彩时停止。陈小青希望收集的云彩最多，请求出最多可以收集多少个不同的云彩。
输入
第 1 行一个正整数 n ；
第 2 行 n 个数 a[i] 代表 i 个时刻云彩的形状 。
n <= 1e6 a[i] <= 1e9
输出
最多能收集不同云彩的个数。
样例输入
5
1 2 3 2 1样例输出
3这题好像很简单 然而比赛没一个做出来（可能是大家都太菜了
用到Vector容器，关于STL平时用的实在太少，唉
AC代码：
#include <iostream> #include <cstring> #include <cmath> #include <cstdio> #include <algorithm> #include <vector> using namespace std; typedef long long ll; const int maxn = 1e6+5; const int mod = 23333; int n; int a[maxn]; vector<int> t[maxn]; bool Find(int x) { int amod = x%mod; vector<int>::iterator it; for(it =t[amod].begin() ; it!=t[amod].end();it++) { if(*it==x) return true; } return false; } void Erase(int x) { int amod = x%mod; vector<int> :: iterator it; for(it =t[amod].begin();it!=t[amod].end();it++) { if(*it==x) { t[amod].erase(it); return; } } } int main() { while(scanf("%d",&n)!=EOF) { for(int i=0;i<1e6;i++) t[i].clear(); int j=1; int ans = 0; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); if(!Find(a[i])) { int amod = a[i]%mod; t[amod].push_back(a[i]); } else { while(a[j]!=a[i]) { Erase(a[j]); j++; } j++; } ans = max(ans,i-j+1); } printf("%d ",ans); } }
B.许小铭的有趣数
时间限制: 1 Sec 内存限制: 128 MB
提交: 14 解决: 6
[提交][状态][讨论版][命题人:201607255]
题目描述
许小铭看到一种有趣的数字。
不含前导零且相邻两个数字之差至少为2的正整数是许小铭的有趣数。
许小铭想知道，在A和B之间，包括A和B，有多少个有趣数。
输入
输入一行包括两个数字A和B
输出
输出一行包含一个整数，表示区间A和B中有趣数的个数
A,B>=1&&A,B<=2000000000
样例输入
25 50样例输出
20思路：数位DP 原题指引：BZOJ 1026
AC代码：
#include <iostream> #include<cstdio> #include<cstring> #include<string> #include<cmath> using namespace std; typedef long long ll; const int maxn = 1e6+5; const int mod = 1e9+7; ll powmod(ll a,ll b) {ll res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} ll dp[20][20]; ll a,b; ll ans; ll s[20]; void Init() { for(int i=0;i<=9;i++) dp[1][i]= 1; for(int i=2;i<=10;i++) { for(int j=0;j<=9;j++) { for(int k=0;k<=9;k++) { if(fabs(j-k)>=2) dp[i][j]+=dp[i-1][k]; } } } } ll yq(int x) { ll ans =0; int len = 0; while(x) { s[++len] = x%10; x/=10; } for(int i=1;i<len;i++) { for(int j=1;j<=9;j++) { ans+= dp[i][j]; } } for(int j=1;j<s[len];j++) { ans+= dp[len][j]; } for(int i=len-1;i>=1;i--) { for(int j=0;j<s[i];j++) { if(fabs(j-s[i+1])>=2) { ans+= dp[i][j]; } if(fabs(s[i]-s[i+1])<2) break; } } return ans ; } int main() { Init(); scanf("%lld%lld",&a,&b); printf("%lld ",yq(b+1)-yq(a)); }
C: 柴小俊的机器人
时间限制: 1 Sec 内存限制: 128 MB
提交: 41 解决: 9
[提交][状态][讨论版][命题人:201607255]
题目描述
柴小俊开始玩他的机器人了。
机器人在一个n*m的矩阵里，柴小俊可以给出操作序列指挥他的机器人，L向左走，R向右走，U向上走，D向下走。在矩阵里有机器人，空地，障碍。当机器人接收到一个行走指令时，如果即将到达的位置为障碍物，那么机器人将留在原地，否则机器人向对应方向走一步，如果其走出边界那么立即死亡。由于操作机器人还处于初级阶段，柴小俊给出的操作序列在传输过程中可能会丢失。比如RUR指令，到机器人那里可能变成RR或者U。因此定义一个操作序列是绝对安全的当且仅当其任意子序列都是安全的。我比较好奇绝对安全的操作的序列最长可以是多长。如果为无穷长输出-1.
输入
第一行一个正整数T，表示数据组数。
接下来一共 T 组数据，每组数据第一行有两个正整数 n,m，表示网格图的大小, 接下来 n 行，每行 m 个字符，表示这张网格图。
其中字符“.”表示空地，“#”表示障碍物，“S”表示机器人所在位置。
输出
一共 T 行，每行一个整数，表示答案。所有数据大于等于0小于等于50 样例输入
3
5 5
#####
#...#
.#S#.
#...#
#####
1 7
S......
5 8
#.######
#.#..S.#
#.#.##.#
#......#
########样例输出
-1
6
-1读题一直想不通这个输出怎么来的，可能是原本英文题直接机翻过来有点问题，代码和题意描述的有点区别
AC代码：
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; typedef long long ll; const int MAXN=1e5+10; const ll mod=1e9+7; char a[55][55]; int n,m; int main() { int T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); if((n==0||m==0)||(n==1&&m==1)) { printf("0 "); continue; } for(int i=0;i<n;i++) scanf("%s",&a[i]); int x,y; for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(a[i][j] == 'S') {x = i ;y =j;} int flag = 0; for(int i=0;i<n;i++) { if(a[i][y]=='#') flag++; } for(int j=0;j<m;j++) { if(a[x][j]=='#') flag++; } if(flag>0) printf("-1 "); else printf("%d ",n+m-2); } }
D: 刘小强的苹果树
时间限制: 1 Sec 内存限制: 128 MB
提交: 16 解决: 2
[提交][状态][讨论版][命题人:201607255]
题目描述
刘小强的河里有n块石头，从1到n，请你帮他计算最多选取m块石头的方法数。
输入
第一行测试样例数T.
每个样例一行，两个数 n，m，(T<=1e5,n<=1e5,m<=1e5)
输出
输出方法数模1e9+7.
样例输入
2
5 2
1000 500样例输出
16
924129523这道题当时做多校的时候就看过原题，一毛一样，然而没补题、、
思路：组合数+莫队 关于莫队还不是很会，挖个坑慢慢补
原题指引： HDU 6333
先放上题解和代码 较详细的题解
AC代码：
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e5+5; const int mod = 1e9+7; ll fac[maxn],inv[maxn]; ll rev2; struct Query{ int L,R,id,block; bool operator < (const Query &p)const{//按照分块排序，再按照右端点排序 if(block == p.block) return R < p.R; return block < p.block; } }Q[maxn]; ll res; ll ans[maxn]; ll q_pow(ll a,ll b){ ll ans = 1; while(b){ if(b & 1) ans = ans * a % mod; b >>= 1; a = a * a % mod; } return ans; }//快速幂取模 ll C(int n,int k){ return fac[n] * inv[k] % mod * inv[n-k] % mod; }//组合数公式 void init(){ rev2 = q_pow(2,mod-2); fac[0] = fac[1] = 1; for(int i = 2; i < maxn; i++){ fac[i] = i * fac[i-1] % mod; }//预处理阶乘 inv[maxn-1] = q_pow(fac[maxn-1],mod-2); for(int i = maxn-2; i >= 0; i--){ inv[i] = inv[i+1] * (i + 1) % mod; }//预处理阶乘的逆元（很巧妙，不需要每次求逆元了） } inline void addN(int posL,int posR){//因为传进来的posL已经加1了，所以求S(posL,posR)=2S(posL-1,posR)-C(posL-1,posR) //而S(posL-1,posR)就是上一次的结果res,故只需要算C(posL-1,posR) res = (2 * res % mod - C(posL-1,posR) + mod) % mod; } inline void addM(int posL,int posR){//因为传进来的posR已经自增完成，res是上一次的结果S(posL,posR-1)故只需要求C(posL,posR) res = (res + C(posL,posR)) % mod; } inline void delN(int posL,int posR){//因为传进来的是后缀自增，所以posL还是原来的值 //那么新的S(posL-1,posR)=(S(posL,posR)+C(posL-1,posR))/2,其中S(posL,posR)就是res res = (res + C(posL-1,posR)) % mod * rev2 % mod; } inline void delM(int posL,int posR){//因为传进来的是后缀自增，所以posR还是原来的值 //那么新的S(posL,posR-1)=S(posL,posR)-C(posL,posR),其中S(posL,posR)就是res res = (res - C(posL,posR) + mod) % mod; } int main(){ int T; init(); int len = (int)sqrt(maxn*1.0); scanf("%d",&T); for(int i = 1; i <= T; i++){ scanf("%d%d",&Q[i].L,&Q[i].R); Q[i].id = i;//记录下查询顺序编号 Q[i].block = Q[i].L / len;//块号 } sort(Q+1,Q+1+T);//排序 res = 2; int curL = 1,curR = 1; for(int i = 1; i <= T; i++){ while(curL < Q[i].L) addN(++curL,curR);//需要算S(curL+1,curR)=2S(curL,curR)-C(curL,curR) while(curR < Q[i].R) addM(curL,++curR);//需要算S(curL,curR+1)=S(curL,curR)+C(curL,curR+1) while(curL > Q[i].L) delN(curL--,curR);//需要算S(curL-1,curR)=(S(curL,curR)+C(curL-1,curT))/2 while(curR > Q[i].R) delM(curL,curR--);//需要算S(curL,curR-1)=S(curL,curR)-C(curL,curR) ans[Q[i].id] = res; } for(int i = 1; i <= T; i++){ printf("%lld ",ans[i]); } return 0; }
E: 田小宏的苦恼
时间限制: 1 Sec 内存限制: 128 MB
提交: 5 解决: 3
[提交][状态][讨论版][命题人:201607327]
题目描述
Tian Xiaohong writes code frequently, so he is familiar with this statement, That is：
for( i = A; i != B; i += C )
No doubt, this for statement starts with i =A and ends with i =B, each time i increases C on the previous value.But restricted by the computer, the type of i contains only n bits and does not contain symbol bits. According to the rules of computer arithmetic, the bit will be discarded when the resulting carry has no place to store it.
Because the value of n is going to be different on different machines, so The number of times the loop body is executed is going to be different, Shahong is very distressed about it.So please write a program to help him solve this problem.
输入
The input contains several sets of data, each of which has four non-negative values, namely A, B, C and n, ending with all being 0, Make sure that 0 ≤n ≤ 32, and 0 ≤ A( B, C ) < 2ⁿ.
输出
Each group outputs an integer t in one line, indicating the number of times the loop body is executed. If it cannot exit the loop, it will output "never", without having to output all being 0.
样例输入
1 1 2 4
2 1 1 3
5 7 11 13
2 3 4 5
0 0 0 0样例输出
0
7
5958
never
唯一一道英文题 被其他题搞的太烦了 直接忽略没看 然而好像就是一道模板题
思路：拓展欧几里得裸模板题 类似POJ 1061 青蛙的约会 改一点点就可以了
AC代码：
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; ll exgcd(ll l,ll r,ll &x,ll &y) { if(r==0){x=1;y=0;return l;} else { ll d=exgcd(r,l%r,y,x); y-=l/r*x; return d; } } int main() { ll a, b, c, k; while(~scanf("%lld%lld%lld%lld",&a,&b,&c,&k)&&a&&b&&c&&k) { ll w = b-a; if(!w){ printf("0 "); continue; } ll l = c; ll r = (ll) 1 << k; ll x, y; ll d = exgcd(l,r,x,y); if(w%d) printf("never "); else printf("%lld ",((x*w/d)%(r/d)+(r/d))%(r/d)); } return 0; }
F: 蔡小庆的后花园
时间限制: 1 Sec 内存限制: 128 MB
提交: 31 解决: 7
[提交][状态][讨论版][命题人:201607255]
题目描述
蔡小庆的后花园里有一个长L米宽w米的草坪，里面有n个喷水装置，每个喷头都装在草坪中心线上（离两边各 w/2米）。我们知道每个喷头的位置（离草坪中心线左端的距离），以及它能覆盖到的浇灌范围。
请问：如果要同时浇灌整块草坪，最少需要打开多少个喷头？
输入
输入包含若干组测试数据。
第一行一个整数 T 表示数据组数；
每组数据的第一行是整数 n、L和 W；
接下来的 n 行，每行包含两个整数，给出一个喷头的位置和浇灌半径（上面的示意图是样例输入第一组数据所描述的情况）。
输出
对每组测试数据输出一个数字，表示要浇灌整块草坪所需喷头数目的最小值。如果所有喷头都打开也不能浇灌整块草坪，则输出 −1 。
对于 100% 的数据，n≤15000
样例输入
3
8 20 2
5 3
4 1
1 2
7 2
10 2
13 3
16 2
19 4
3 10 1
3 5
9 3
6 1
3 10 1
5 3
1 1
9 1样例输出
6
2
-1比赛后面在狂怼这题 一直WA，条件判断那里有个小地方错了，到结束都没A
思路很简单就是用贪心一直找覆盖范围最右的圆进行更替，注意double类型
AC代码：
#include <iostream> #include<cstdio> #include<cstring> #include<string> #include<cmath> #include<algorithm> using namespace std; typedef long long ll; const int maxn = 1e6+5; const int mod = 1e9+7; ll powmod(ll a,ll b) {ll res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} ll dp[20][20]; double X,R; double W,L; int n; ll s[20]; struct node { double l,r; }a[maxn]; bool cmp(node a,node b) { return a.l<b.l; } int main() { int t; scanf("%d",&t); while(t--) { memset(a,0,sizeof(a)); scanf("%d%lf%lf",&n,&L,&W); int j =0; for(int i=1;i<=n;i++) { scanf("%lf%lf",&X,&R); if(R*2 <= W) continue; ++j; a[j].l =X -sqrt(R*R-W*W/4.0); a[j].r =X +sqrt(R*R-W*W/4.0); } sort(a+1,a+j+1,cmp); int ans = 0; double x = 0; double y = 0; while(x<L) { ans++; y = x; for(int i =1;i <=j;i++) { if(a[i].r >x && a[i].l <=y) //错误代码: if(a[i].r>x && a[i].l <=x) { x = a[i].r; } } if(x==y) {ans =-1;break;} } printf("%d ",ans); } }
好好学习，天天向上