转载请注明出处,谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents
by---cxlove
不科学,CF又跪了。。。水题也能写半天。。。。
感谢Dshawn的指导~~~~~~~
A. Tiling with Hexagons
给出a,b,c,根据图中的形状判断有多少块。
分为三个部分,总和就是b*c+(a-1)*(b+c-1)
也可以是不断向内一层层的分解。
最外层为2*(b+c+a)-6。
而里面一层为a-1,b-1,c-1,但是注意如果出现边为1的话,就不能这么统计了
不过边为1刚好就是一个矩形
while(a>1&&b>1&&c>1){
ans+=2*(a+b+c)-6;
a--;b--;c-;;
}
ans+=a*b*c;
B. Forming Teams
有N个人,组成两队比赛,每一队中不能有敌对状态。
由于每个人最多有两个敌对的,所以要么是单链,要么是简单的环,要么就是孤立状态。
孤立状态肯定不用考虑,随便往哪队放都可以
对于单链也不需要考虑,因为总是可以完整的分为两队
对于环先考虑偶数环,两两交错,也是可以分为两队
但是奇数环就不可以了,总有一个人首尾相接,不能去任何一队
所以结果就是如果有奇数环,总数减1,最后还需要判断奇偶性
C. Hiring Staff
开始是固定的,K为几,那么就得有K个人从第一天开始,然后前n天都不用考虑,不过得有一个人去交接钥匙,贪心处理,总是尽可能靠后,那就是第n天,从第n+1天只有一个人上班,如果k>1的话,就需要安排k--1个人从n+1天开始,如果k为1,那么就是从2*n-1去交接钥匙。总之每一个人都尽可能靠后,贪心模拟一下,直到第n+m+1天第一批人回来上班。
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#define N 1000000000
#define inf 1<<29
#define MOD 9973
#define LL long long
#define eps 1e-7
using namespace std;
int n,m,k;
vector<int>v;
int main(){
while(scanf("%d%d%d",&n,&m,&k)!=EOF){
v.clear();
for(int i=0;i<k;i++)
v.push_back(1);
v.push_back(n);
for(int i=1;i<k;i++)
v.push_back(n+1);
int l=2*n;
if(k==1)
l--;
while(l<n+m+1){
v.push_back(l);
if(l+1==n+m+1) break;
for(int i=1;i<k;i++)
v.push_back(l+1);
l+=n;
if(k==1) l--;
}
printf("%d\n%d",v.size(),v[0]);
for(int i=1;i<v.size();i++)
printf(" %d",v[i]);
puts("");
}
return 0;
}
D. Spider's
Web
直接对于每一个区域,每一个小扇形进行枚举,二分找到对于两边的数目,比较
感觉这样不是很慢吗,哎。。。。。n*k,1000*100000*log(100000
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#define N 1000000000
#define inf 1<<29
#define MOD 9973
#define LL long long
#define eps 1e-7
#define pb(a) push_back(a)
#define ub(v,a) upper_bound(v.begin(),v.end(),a)
using namespace std;
int main(){vector <int> v[1001];
int n,k,r;
while(scanf("%d",&n)!=EOF){
for(int i=1;i<=n;i++){
v[i].clear();
scanf("%d",&k);
while(k--){
scanf("%d",&r);
v[i].pb(r);
}
sort(v[i].begin(),v[i].end());
}
int ans=0;
for(int i=1;i<=n;i++){
int pre=i-1; pre=pre==0?n:pre;
int next=i+1; next=next==n+1?1:next;
for(int j=1;j<v[i].size();j++){
int x=ub(v[pre],v[i][j])-ub(v[pre],v[i][j-1]);
int y=ub(v[next],v[i][j])-ub(v[next],v[i][j-1]);
if(x!=y) ans++;
}
}
printf("%d\n",ans);
}
return 0;
}
E. Martian Luck
有个重要的结论:在k进制下个位数字之和相当于那个数字转化成十进制以后mod(k-1),0的话就是k-1
那么就能直接处理了,取前i项和的模数。用map记录,然后遍历一遍,就可以了。
不过由于k-1,0都最终记为0,所以这里要处理一下,如果b既不是0,也不是k-1的话,那就无所谓了。
我们通过原数据,找一下所有0的数目,因为这个比较方便,
那么如果b就是0,那么就是我们最后统计的数目
如果b为k-1那么我们要把原来统计的去掉b为0的情况。
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#define N 1000000000
#define inf 1<<29
#define MOD 9973
#define LL long long
#define eps 1e-7
#define pb(a) push_back(a)
#define ub(v,a) upper_bound(v.begin(),v.end(),a)
using namespace std;
int sum[100005],a[100005];
int main(){
int k,b,n;
while(scanf("%d%d%d",&k,&b,&n)!=EOF){
int m=k-1,pre=0;
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
pre=(pre+a[i])%m;
sum[i]=pre;
}
map<int,int>mmap;
mmap.clear();
LL ans=0;
mmap[0]++;
for(int i=0;i<n;i++){
int t=(m+sum[i]-b)%m;
if(mmap.count(t))
ans+=mmap[t];
mmap[sum[i]]++;
}
LL ret=0;
for(int i=0;i<n;i++){
if(a[i]==0){
int j=1;
while(i+j<n&&a[j+i]==0) j++;
ret+=(LL)j*(j+1)/2;
i+=j;
}
}
if(b==0) ans=ret;
else if(b==k-1) ans-=ret;
printf("%I64d\n",ans);
}
return 0;
}
分享到:
相关推荐
Codeforces Round #723 (Div. 2).md
上面代码跑出来的dp[n][m]是0,然后从(1,1)(1,2)(2,2)(2,3)这样的相与值是k (看懂ans+k是啥应该就懂了) 代码: int main() { std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); int ans=(1&...
传送门 题意: 开始位置在0,问能否跳到n+1位置 每步只能跳d 在1——n每个位置有方向,L,R,求d的最小值 思路: 只用找相邻两个R之间的最大值即可 代码: #include #include ...typedef long long l
就是把所有相等的数放到一个vector里,如果他出现大于2次,看最远的间距是否大于2即可,找到一个就可以 代码: #include #include #include #include #include #include #include #include #include #include #...
长度为n的字符串包含n−2n−2n−2个aaa和222个bbb,求按照字典序排列输出第kkk个字符串 解题思路 第一个bbb在倒数第二位有1个字符串,在倒数第三位有2个字符串…在倒数第nnn位时有n−1n-1n−1个字符串 可以根据第一...
E. Cyclic Components 题目链接-E. Cyclic Components 题目大意 给你nnn个点和mmm条边,求所构成图中单圈环的个数 ...并查集并查集并查集 很明显单圈环每个点的度都为222,所以我们可以用数组cnt[]记录每个点的度,...
Codeforces Round #629 (Div. 3) E.Tree Queries (DFS) 思路:若ai 在路径上 ,则ai的父结点一定在路径上,若ai是路径上某个结点的子结点,则ai的父结点一定在路径上,综上只需考虑ai的父节点就行了。对每个ai判断...
给两两节点放一个数字(0~n-2 唯一) 给你一棵树,求所有任意两节点相连的路以外的路上的数字的最小值最小 思路 构造 若一个点连了三条边及以上,则这个点的边从最小值开始赋值。其他边从最大点开始赋值。 证明:一...
给一个长度为n的数组,两种操作,一个是把任意一个ai变成ai+2a_i变成a_i+2ai变成ai+2,另一个是如果所有数都大于0,可以把所有数减1,问通过这些操作能否把所有数变为0 思路: 如果任意两个数之差为奇数,那么就...
输入一个正整数x,找出这样的2个正整数a和b,使得gcd(a,b)+lcm(a,b)=x 解题思路 找最特殊的情况a=1,b=x-1即可 这样a,b两个数最大公因数为1,最小公倍数x-1,满足题意√ 附上代码 #include #define int long long #...
B. Longest Palindrome time limit per test1 second memory limit per test256 megabytes inputstandard input outputstandard output Returning back to problem solving, Gildong is now studying about ...
将所有数字看成2进制,从最高位看起,如果第i位上为1的数只有一个的话,那么这个数必然对答案有贡献,就把它排在第一个,后面任意排。 例:11,6,4,0 二进制表示为:1011,110,100,0 右起第四位为1的只有1011,...
C(n-2,i-1)*C(j-1,n-2)*(i-1) __ j: n-1 -> m 我们发现内层循环,每次只是j加一,我们就可以只用一次组合数剩下的用差量表示 对于外层循环同理 只有(i-1) * C(n-2,i-1) i会每次加一。我们也只算一次剩下的用差量...
传说门 刚好今晚是中国场! 其实这道题比较水,但当时思路错,一心想着化简公式,浪费了好多时间a....#pragma GCC optimize(2) #include #define ll long long #define endl '\n' using namespace std; const int manx=
传送门 题意: 找规律,题意就是有多少种方式填充该图形 画两个就发现,输出n即可 代码: #include #include #include #include #include #include #include #include ...#define SZ(x) ((int)(x)
A #include using namespace std; typedef long long ll; int main(){ int t; cin>>t; while(t--){ ll x; cin>>x; cout<<1>>t; while(t--){ st.clear(); ll n; cin >>n;... ll re
题目链接:B. Longest Palindrome 题目 Returning back to problem solving, Gildong is now studying about palindromes. He learned that a palindrome is a string that is the same as its reverse....
惭愧,前几天刚学的dfs序判祖先关系都忘了用。。 这题我们先把所有点都变成父亲节点(根节点不变),这样只需要判所有节点是否在一条链上。 由于判断x是y的祖先:需要满足:st[x]<...const int M = 2e5+