转载请注明出处,谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents
by---cxlove
没想到提交的4题都过了, 第一次,rate也涨了,终于紫了。
总结:小错误太多
A:问距离最近的城市是不是唯一。唯一则输出标号,就是个排序
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<string>
#define inf 1<<30
#define eps 1e-7
#define LD long double
#define LL long long
using namespace std;
struct Node{
int idx,num;
}a[100005];
bool cmp(Node n1,Node n2){
return n1.num<n2.num;
}
int main(){
int n;
while(scanf("%d",&n)!=EOF){
for(int i=0;i<n;i++){
scanf("%d",&a[i].num);
a[i].idx=i+1;
}
if(n==1){
printf("1\n");
continue;
}
sort(a,a+n,cmp);
if(a[0].num==a[1].num)
printf("Still Rozdil\n");
else
printf("%d\n",a[0].idx);
}
return 0;
}
B:每次可以选择位置i后的所有数加1,则最少要做多少次操作,使得数列非递减。
最少操作肯定是保证后者不比前者小即可。
从头到尾遍历,不需要做一次操作, 把之后的所有数都加1,相邻之间的相对差不变。唯一一个1A。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<string>
#define inf 1<<30
#define eps 1e-7
#define LD long double
#define LL __int64
using namespace std;
int a[100005];
int main(){
int n;
while(scanf("%d",&n)!=EOF){
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
LL ans=0;
for(int i=1;i<n;i++)
if(a[i]<a[i-1])
ans+=a[i-1]-a[i];
printf("%I64d\n",ans);
}
return 0;
}
C:头尾相同的数称为XX数,问区间[l,r]有多少个XX数。预处理+瞎搞,其实有很简单的做法,直接得到公式,弱爆了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<string>
#define inf 1<<30
#define eps 1e-7
#define LD long double
#define LL __int64
using namespace std;
LL l,r;
LL dp[20];
LL sum[20];
int countdigit(LL num){
int ans=0;
while(num){
num/=10;
ans++;
}
return ans;
}
int firstdigit(LL num){
while(num>=10)
num/=10;
return num;
}
int lastdigit(LL num){
return num%10;
}
int main(){
dp[1]=dp[2]=9;
sum[1]=10;sum[2]=100;
LL tmp=10;
for(int i=3;i<20;i++){
dp[i]=9*tmp;
tmp=tmp*10;
sum[i]=sum[i-1]*10;
}
while(scanf("%I64d%I64d",&l,&r)!=EOF){
int a=countdigit(l);
int b=countdigit(r);
LL ans=0;
for(int i=a+1;i<=b;i++)
ans+=dp[i];
int first=firstdigit(l);
int last=lastdigit(l);
if(a==1){
ans+=10-first;
}
else if(a==2){
ans+=9-first;
if(first>=last)
ans++;
}
else{
if(first>=last){
ans+=sum[a-2]-(l/10)%sum[a-2];
for(int i=first+1;i<=9;i++)
ans+=sum[a-2];
}
else{
for(int i=first+1;i<=9;i++)
ans+=sum[a-2];
ans+=sum[a-2]-(l/10)%sum[a-2]-1;
}
}
first=firstdigit(r);
last=lastdigit(r);
if(b==1){
ans-=9-last;
}
else if(b==2){
ans-=9-first;
if(last<first)
ans--;
}
else{
if(first>last){
ans-=sum[b-2]-(r/10)%sum[b-2];
for(int i=first+1;i<=9;i++)
ans-=sum[b-2];
}
else{
ans-=sum[b-2]-((r/10)%sum[b-2]+1);
for(int i=first+1;i<=9;i++)
ans-=sum[b-2];
}
}
printf("%I64d\n",ans);
}
return 0;
}
D:n张牌,牌的两面有颜色,最少多少次操作使得某种颜色朝上的数量超过半数,map或者离散化
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<map>
#include<string>
#define inf 1<<30
#define eps 1e-7
#define LD long double
#define LL __int64
#define maxn 1000000005
using namespace std;
map<int,int>m1;
map<int,int>m2;
int main(){
int n,u,v;
scanf("%d",&n);
int ans=n+10;
for(int i=0;i<n;i++){
scanf("%d%d",&u,&v);
if(u!=v)
m1[u]++;
m1[v]++;m2[u]++;
if(m1[u]>=(n+1)/2)
ans=min(ans,max(0,(1+n)/2-m2[u]));
if(m1[v]>=(n+1)/2)
ans=min(ans,max(0,(1+n)/2-m2[v]));
}
if(ans>n)
printf("-1\n");
else
printf("%d\n",ans);
return 0;
}
E:概率题,对于每一组a[i]==b[j],判断出现在多少个子集内,当时看错题目了,错误理解了子集的概念。膜拜詹姐
#include<iostream>
#include<cstdio>
#include<cstring>
#define LD long double
#define LL __int64
#define M 200005
int n;
char str1[M],str2[M];
int main(){
while(scanf("%d%s%s",&n,str1,str2)!=EOF){
LD ans=0;
for(int ch='A';ch<='Z';ch++){
int j=n-1;
LD p=0;
for(int i=n-1;i>=0;i--){
if(str1[i]==ch){
while(j>i){
if(str2[j]==ch)
p+=n-j;
j--;
}
ans+=p*(i+1);
}
}
j=n-1;
p=0;
for(int i=n-1;i>=0;i--){
if(str2[i]==ch){
while(j>=i){
if(str1[j]==ch)
p+=n-j;
j--;
}
ans+=p*(i+1);
}
}
}
printf("%.10f\n",(LD)ans*6/((LD)n*(n+1)*(2*n+1)));
}
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+