A - Display The Number http://codeforces.com/contest/1295/problem/A
思路: 两个就可以组成 1, 那么四个就可以组成 11, 六个就可以组成最大 111, 三个就可以组成 7, 五个那么就是(3+2), 组成 71, 所以当是偶数的话就组成全部是 1 就行, 奇数就是最前面放 7, 后面全放 1
- #include<iostream>
- #include<cstdio>
- #include<algorithm>
- #include<cstring>
- #include<queue>
- #include<cmath>
- using namespace std;
- const int maxn=1000+10;
- int main()
- {
- int a[6]={6,7,3,4,2};
- int n,nn;
- scanf("%d",&n);
- for(int i=0;i<n;i++)
- {
- scanf("%d",&nn);
- if(nn%2==0)
- {
- int t=nn/2;
- for(int j=0;j<t;j++)
- printf("1");
- printf("\n");
- } else
- {
- printf("7");
- int tt=nn/2-1;
- for(int jj=0;jj<tt;jj++)
- printf("1");
- printf("\n");
- }
- }
- return 0;
- }
- B - Infinite Prefixes http://codeforces.com/contest/1295/problem/B
思路:.. 没想出. 后来看了原来可以用前缀和写, 把 1 变成 - 1,p[i+1]=p[i]-1;0 的位置变成 1,p[i+!]=p[i]+1; 字符串 s 的长度为 Len, 那么 p[Len]就是这个单个字符串的前缀和
1. 现在判断有无穷个情况, 当字符串有个位置的值为 x 时, 此时前缀和又为 0, 那么这肯定就是无穷的, 可以加无穷多个这样的字符串
2. 当前位置值为 x 时, 但是前缀和不为 0, 那么这个前缀就满足了条件, 个数可以 + 1
3. 当前位置值 < x 时并且 p[Len]>0, 可以再在后面加一个这样的字符串, 同样的位置的值就是 p[Len]+p[i],
可以再加, 所以 (x-p[i])%p[Len)==0) 时(可以加一定数量的字符串), 那么就满足条件 + 1;
3. 同理, 当前位置值 > x 时并且 p[Len]<0, 再在后面加这样的字符串时, 同样的位置的值就是 p[Len]+p[i],
所以(p[i]-x)%(-p[Len])==0), 那么也满足条件 + 1;
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const int maxn = 1e5;
- int main(){
- int T;
- scanf("%d",&T);
- for(int i=0;i<T;i++)
- {
- int len;
- ll x;
- cin>>len>>x;
- string s;
- cin>>s;
- int Len=s.length();
- ll p[maxn];
- p[0]=0;
- for(int i=0;i<Len;i++)
- {
- if(s[i]=='0')
- p[i+1]=p[i]+1;
- else
- p[i+1]=p[i]-1;
- }
- ll he=p[Len];
- int sum=0;
- bool flag=false;
- for(int i=0;i<=Len;i++)
- {
- if(p[i]==x)
- sum++;
- if(p[i]==x&&he==0)
- flag=true;
- if(i!=0&&he>0&&p[i]<x&&(x-p[i])%he==0)
- sum++;
- if(i!=0&&he<0&&p[i]>x&&(p[i]-x)%(-he)==0)
- sum++;
- }
- if(flag)
- printf("-1\n");
- else
- printf("%d\n",sum);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3400000.html