赞
踩
这次题解有点简陋,后面会慢慢更新优化,先凑合着看。有问题在群里或者评论区里直接说就行。
四舍五入取整,只需要判断小数点最后一位就可以。考查对字符串的处理。用long double也可以过。
n的范围 0 < n <= 1e18。double的精度为2^52-1=4503599627370495,只有15位数左右,所以会出问题,long double的精度大概在19位左右,就可以过了(本来想把long double也卡掉的,后来想想算了…)。字符串处理的解法就是,通过小数点分割就行,求出整数部分的值,再判断小数点后一位的值的大小,大于等于5就加一。
字符串处理:
#include<bits/stdc++.h> using namespace std; typedef long long ll; int main(){ string str; cin >> str; ll ans = 0, f = 0; while(str[f] != '.' && f<str.size()) { ans = ans*10 + str[f]-'0'; f++; } f++; if(str[f] >= '5') ans++; cout << ans; }
long double 解法
#include<bits/stdc++.h>
using namespace std;
int main(){
long double a;
cin >> a;
// printf会自动四舍五入
printf("%.0Lf",a);
}
考察选择语句的使用。
#include<bits/stdc++.h> using namespace std; typedef long long ll; int main(){ int t; cin >> t; while(t--){ int op, a, b; cin >> op >> a >> b; if(op == 1) cout << a+b <<'\n'; else if(op == 2) cout << a-b <<'\n'; else if(op == 3) cout << a*b <<'\n'; else if(op == 4) cout << a/b <<'\n'; } }
考查排序函数的使用。改编自前几年的省赛原题。cmp比对函数写好后,再直接排序输出就行。
#include<bits/stdc++.h> using namespace std; typedef long long ll; string str[200050]; bool cmp(string a, string b){ reverse(a.begin(),a.end()); reverse(b.begin(),b.end()); string c, d; int f = 0; for(int i = 0; i<a.size(); i++){ if(a[i] != '0') f = 1; if(f) c+=a[i]; } f = 0; for(int i = 0; i<b.size(); i++){ if(b[i] != '0') f = 1; if(f) d+=b[i]; } if(c == d) return a.size()<b.size(); if(c.size() == d.size()) return c < d; return c.size() < d.size(); } int main() { int a, b, n; cin >> a >> b; n = b-a+1; for(int i = 0; a<=b; i++,a++){ str[i] = to_string(a); } sort(str,str+n, cmp); for(int i = 0; i<n; i++){ if(i != 0) cout << " "; cout << str[i]; }; }
试几个数就能看出来规律。大概就是
n%4 == 1 Either
n%4 == 2 Odd
n%4 == 3 Either
n%4 == 0 Even
证明过程也很简单,略了。
#include<bits/stdc++.h>
using namespace std;
void solve(){
int n;
cin >> n;
if(n%2) cout << "Either" << endl;
else if((n/2)%2) cout << "Odd" << endl;
else cout << "Even" << endl;
}
int main(){
int t;
cin >> t;
while(t--) solve();
}
贪心的往下减就行。题目要求从1开始。它每次减的可以跟原来一样,也可以翻倍。
为了让我们减的次数最小,我们肯定是能翻倍就翻倍。
怎么看能不能翻倍呢?
由于你翻倍之后至少都要减它,所以只有 当前n的值是 翻倍后的数的倍数时,才能翻倍,否则就一直减。
#include<bits/stdc++.h> using namespace std; typedef long long ll; void solve(){ int n, ans = 0, f = 1; cin >> n; while(n){ n -= f; ans++; if(n % (f*2) == 0) f = f*2; } cout << ans << '\n'; } int main(){ int t; cin >>t; while(t--) solve(); }
没必要每次询问都判断这个串是不是回文串,每次询问只更改一个数,因此只需要记着上一次的状态,再加上这次修改的状态就是可以判断是不是回文串。
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main(){ string str; char c; int q, a, cnt = 0; cin >> str >> q; int n = str.size(); for(int i = 0; i < n/2; i++){ if(str[i] == str[n-i-1]) cnt++; } while(q--){ cin >> a >> c; int f = 0; if(str[a-1] == str[n-a]) f = 1; str[a-1] = c; if(str[a-1] == str[n-a]){ if(f == 0) cnt++; }else{ if(f == 1) cnt--; } if(cnt == n/2) cout << "Yes\n"; else cout << "No\n"; } }
求最大和,并要求是偶数。直接求所有数的和,如果和是偶数,直接就是答案,如果是奇数,就减去所有数中最小的那个奇数,就变成偶数了。
#include<bits/stdc++.h> using namespace std; typedef long long ll; int main(){ int n, a, mi = 1e9+10; ll sum = 0; cin >> n; for(int i = 1; i<= n; i++){ cin >> a; sum += a; if(a&1) mi = min(mi, a); } if(sum&1) sum -= mi; cout << sum; }
某一年蓝桥杯原题,改了改题面,具体题解请看
K倍区间
求区间[l,r]的和是k的倍数的个数。求区间和,我们可以通过前缀和来求出。我们规定sum[i]表示第1个元素到第i个元素的和。那么sum[r] - sum[l-1]就是区间[l,r]的和。区间[l,r]的和是k的倍数即(sum[r] - sum[l-1])%k == 0 即sum[r]%k == sum[l-1]%k
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e5+10; int arr[maxn], mp[maxn]; int main(){ ll n, k, a; cin >> n >> k; for(int i = 1; i<=n; i++){ cin >> a; arr[i] = (arr[i-1]+a) % k; mp[arr[i]]++; } mp[0]++; ll ans = 0; for(int i = 0; i < k; i++){ ans += 1ll*(mp[i]-1)*mp[i]/2; } cout << ans; }
题目大意: 给一棵边带权的树,你可以将一条边换个位置,换完之后还得是一棵树,要求换完之后树的直径最小。
大致思路:很显然,最优解中去掉的那条边一定在原先这棵树的直径上,否则交通费用最大的两个点之间距离没有缩短。n这么小,可以枚举每条去掉的边。
去掉一条边后原图变为两棵树,将这两棵树连起来后,交通费用最大为
max{第一棵树的直径,第二棵树的直径,两棵树的“重心”到最远结点的距离和+这条边的长度}这里所说的树的“重心”指树中的一个结点,它到树中任意节点的距离最大值 最小
树的直径求法:
随便找一个点u,找到树中到它距离最远的点v。再找到树中到v距离最远的点w,v到w的距离即为树的直径。还有O(n)的解法,就不说了。
#include<bits/stdc++.h> using namespace std; const int N=5005; const int inf=1000000000; int n,cnt,last[N],mn,val,mx1[N],mx2[N],bel1[N],bel2[N]; struct edge{int to,next,w;}e[N*2]; int read(){ int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } void addedge(int u,int v,int w){ e[++cnt].to=v;e[cnt].w=w;e[cnt].next=last[u];last[u]=cnt; e[++cnt].to=u;e[cnt].w=w;e[cnt].next=last[v];last[v]=cnt; } void get_dia(int x,int fa){ mx1[x]=mx2[x]=0; for (int i=last[x];i;i=e[i].next){ if (e[i].to==fa) continue; get_dia(e[i].to,x); if (mx1[e[i].to]+e[i].w>mx1[x]) mx2[x]=mx1[x],mx1[x]=mx1[e[i].to]+e[i].w; else if (mx1[e[i].to]+e[i].w>mx2[x]) mx2[x]=mx1[e[i].to]+e[i].w; } val=max(val,mx1[x]+mx2[x]); } void get_cen1(int x,int fa){ mx1[x]=mx2[x]=0; for (int i=last[x];i;i=e[i].next){ if (e[i].to==fa) continue; get_cen1(e[i].to,x); int v=mx1[e[i].to]+e[i].w,id=e[i].to; if (v>mx1[x]) mx2[x]=mx1[x],bel2[x]=bel1[x],mx1[x]=v,bel1[x]=id; else if (v>mx2[x]) mx2[x]=v,bel2[x]=id; } } void get_cen2(int x,int fa){ mn=min(mn,mx1[x]); for (int i=last[x];i;i=e[i].next){ if (e[i].to==fa) continue; int v,to=e[i].to; if (bel1[x]==e[i].to) v=mx2[x]+e[i].w; else v=mx1[x]+e[i].w; if (v>mx1[to]) mx2[to]=mx1[to],bel2[to]=bel1[to],mx1[to]=v,bel1[to]=x; else if (v>mx2[to]) mx2[to]=v,bel2[to]=x; get_cen2(e[i].to,x); } } int main(){ n=read(); for (int i=1;i<n;i++){ int x=read(),y=read(),z=read(); addedge(x,y,z); } int ans=inf; for (int i=1;i<n;i++){ int x=e[i*2-1].to,y=e[i*2].to,z=e[i*2].w; val=0;get_dia(x,y);get_dia(y,x); mn=inf;get_cen1(x,y);get_cen2(x,y); int tmp=mn; mn=inf;get_cen1(y,x);get_cen2(y,x); val=max(val,tmp+mn+z); ans=min(ans,val); } printf("%d",ans); return 0; }
暴力求就完事了,这题不难,可能是因为放到最后了,就没人写了。不过时间久远,我也不知道我这代码写的是什么鬼玩意,后续再写具体一点。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1005; double arr[N]; int main(){ int n; ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); while(cin >> n){ for(int i = 0; i<n; i++) cin >> arr[i]; int f = 0; for(int i = 1; i < n; i++){ double k = (1.0*arr[i]-arr[0])/(1.0*i); double b = 1.0*arr[0]; map<double, int> mp; mp[b] = 1; for(int j = 0; j < n; j++){ if(j == i) continue; mp[1.0*arr[j]-k*j] = 1; if(mp.size() >= 3) break; } if(mp.size() == 2){ f = 1; break; } } if(f == 0) for(int i = 2; i < n; i++){ double k = (1.0*arr[i]-arr[1])/(1.0*i-1); double b = 1.0*arr[1] - k; map<double, int> mp; mp[b] = 1; for(int j = 0; j < n; j++){ // if(j == i) continue; mp[1.0*arr[j]-k*j] = 1; if(mp.size() >= 3) break; } if(mp.size() == 2){ f = 1; break; } } if(f || n == 2) cout << "Yes" << endl; else cout << "No" << endl; } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。