A
solution:
找规律题
n = 0 , a = 1 , b = 0
n = 1 , a = 2 , b = 1
n = 2 , a = 3 , b = 2
n = 4 , a = 5 , b = 3
n = 5 , a = 8 , b = 5
递推式: b[i] = a[i-1],a[i] = b[i] + b[i-1];
std：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll a[100],b[100];
void solve(){
a[0] = 1,b[0] = 0;
a[1] = 2,b[1] = 1;
for(int i=2;i<=90;i++){
b[i] = a[i-1];
a[i] = b[i] + b[i-1];
}
return ;
}
int main()
{
solve();
int t;
cin>>t;
while(t--){
int n;
cin>>n;
cout<<a[n] + b[n]<<endl;
}
return 0;
}B
solution:
这题赛后又一次重判了，大家记得再交一发，解法就是stack模拟进栈出栈过程
std：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
stack<char> sta;
int main()
{
string s;
cin>>s;
if(s.length() == 0){
cout<<"Yes"<<endl;
return 0;
}
int l = s.length();
for(int i=0;i<l;i++){
if(sta.empty()){
sta.push(s[i]);
}else{
int flag = 0;
char c = sta.top();
if(c == '[' && s[i] == ']'){
sta.pop();
}
else if(c == '(' && s[i] == ')'){
sta.pop();
}
else if(c == '{' && s[i] == '}'){
sta.pop();
}
else{
sta.push(s[i]);
}
}
}
if(sta.size() == 0){
printf("Yes\n");
}else{
printf("No\n");
}
return 0;
}C
solution:
这题做法很多，尺举法，指针，我是记录每个不为0且长度大于等于k的区间，枚举每个区间，类似尺举，一定要记得乘法逆元，忘逆元wa了一发0.0
乘法逆元：a/b mod c = pow_mod(a,c) * pow_mod(b , c-2) %c;
std：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 200005;
const ll mod = 998244353;
ll pow_mod(ll a,ll b)
{
ll ans = 1;
while(b){
if(b&1)
ans = ans*a%mod;
a = a*a%mod;
b>>=1;
}
return ans;
}
ll a[maxn];
struct node{
int l ,r;
};
node b[maxn];
int main()
{
int n,k;
scanf("%d %d",&n,&k);
int l = 0,r = 0,cnt = 0;
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
if(a[i] == 0){
int len = i-l-1;
if(len >= k){
b[++cnt].l = l+1;
b[cnt].r = i-1;
}
l = i;
}
}
if(n-l >= k){
b[++cnt].l = l+1;
b[cnt].r = n;
}
ll ans = 0;
for(int i=1;i<=cnt;i++)
{
int l = b[i].l;
int r = b[i].r;
ll cnt = 1;
for(int j=l;j<=l+k-1;j++){
cnt *= a[j];
cnt %= mod;
}
ans = max(ans , cnt );
for(int j=l+k;j<=r;j++)
{
cnt = cnt%mod*(pow_mod(a[j-k] , mod-2)%mod)%mod;
cnt *= a[j];
cnt %= mod;
ans = max(ans , cnt);
}
}
cout<<ans<<endl;
return 0;
}
D
solution:
异或前缀和
设pre数组是异或前缀和，如果[l,r]是符合的，那么肯定有pre[l-1]^pre[r] = 0,只需要在输入的时候用一个map记录一下异或和
std：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 200005;
ll n,a[maxn],ans = 0,cnt = 0;
map<ll ,int> mp;
int main()
{
int n;
mp[0] = 1;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%lld",&a[i]);
cnt ^= a[i];
ans += mp[cnt];
mp[cnt] += 1;
}
cout<<ans<<endl;
return 0;
}
E
solution:
贪心模拟
贪心模拟，先记录加号的个数k，可以想象将所有的数字从9-1往k+1个数组里加，这样保证小号在前，大的在最后面，最后累加进位，模拟字符串相加即可
std：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 500005;
char s[maxn];
int a[11],ans[maxn];
int main()
{
scanf("%s",s+1);
int l = strlen(s+1),cnt = 1;
for(int i=1;i<=l;i++){
if(s[i] >= '1' && s[i] <= '9'){
a[s[i]-'0']++;
}else{
cnt++;
}
}
int pos = 0,k = 0,flag = 0;
for(int i=10;i>=1;i--){
while(a[i]){
ans[k] += i;
a[i]--;
pos = (pos + 1)%cnt;
if(pos == 0){
k++;
}
}
}
for(int i=0;i<maxn;i++){
ans[i+1] += ans[i]/10;
ans[i]%=10;
}
for(int i=maxn;i>=0;i--){
if(flag || ans[i]){
printf("%d",ans[i]);
flag = 1;
}
}
return 0;
}
F
solution:
听着是个树上博弈，其实是个找规律题
首先这是一颗树，任意两点间的距离固定。我们考虑两个人如何才能获胜，肯定是往对方的方向走，让对方无路可走，你可以这样理解，牛牛想获胜，往牛妹的方向走，如果牛牛走道牛妹的跟前，牛妹无法向牛牛的方向移动，哪只能往叶子节点的方向移动了吧，那牛牛就跟在牛妹后面，最后肯定是牛牛堵住了牛妹，相反的就是牛妹走到了牛牛跟前，牛牛无路可走。。。
如果相离的距离为偶数，牛牛必胜（牛牛先手走，距离为2，牛牛走一步到达必胜局面），相离的距离为奇数，牛妹必胜（情况相反）。所以本题就是让你找树上距离为偶数的不同点的个数，
std：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int a[1000005];
int b[3];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
int main()
{
int n,x;
n = read();
a[1] = 0;
b[1] = 1ll*1;
for(int i=2;i<=n;i++){
x = read();
a[i] = a[x] + 1;
if(a[i]%2){
b[0]++;
}else{
b[1]++;
}
}
printf("%lld\n",1ll*b[0]*(b[0]-1) + 1ll*b[1]*(b[1]-1));
return 0;
}G
solution:
二分期末分数所占的比例，对于每一种比例x，判断其是否可行。
判断可行的方法是，求优秀人数的期望。根据x可以求出来平时成绩所占的比例，如果平时成绩×(1.0 - x)大于等于90，这个人一定是优sum = sum + 1，如果不满足这个条件，就求一下离90差多少分，根据差值和占比x求出原来期末成绩，只要成绩比这个大或者等于，并且在90之间都可行，所以成绩的区间就是(90 - s)，根据这个区间在0到90所占的比例就求出来了这个人优秀的概率p，sum += p，最后sum的和就是优秀人数的期望值，判断期望值和n/10的大小，然后改变二分上下限
std：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
int x,n,sum = 0;
cin>>n;
for(int i=0;i<n;i++){
cin>>x;
sum += x;
}
double ans = sum - 90*n;
printf("%.2lf",(ans/(9*n+ans)*100));
printf("%\n");
return 0;
}
京公网安备 11010502036488号