牛客寒假算法基础训练营day-3
只补了A-E，有机会再补后面的
官方题解地址：https://ac.nowcoder.com/discuss/365889?type=101&order=0&pos=2&page=3&channel=-1
A.欧几里得
gcd(1,0) -----------------------------------------------answer = 0
gcd(2,1) - gcd(1,0) ---------------------------------answer = 1
gcd(3,2) - gcd(2,1) - gcd(1,0) --------------------answer = 2
gcd(4,3) - gcd(3,2) - gcd(2,1) - gcd(1,0) ------answer = 3
....
这是一个f[0] = 1,f[1] = 3,f[2] = 5,f[3] = 8...的斐波那契数列，所以f[n] = f[n-1] + f[n-2]
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long LL;
LL dp[100];
int main()
{
int T;
cin>>T;
dp[2] = 5;
dp[1] = 3;
dp[0] = 1;
for(int i = 3; i<=100; i++) dp[i] = dp[i-1] + dp[i-2];
while(T--)
{
int n;
cin>>n;
cout<<dp[n]<<endl;
}
return 0;
}
B.括号序列
数据好像被加强了，用stack好像T了，数组模拟一下栈就ok了
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <string>
#include <stack>
using namespace std;
const int N = 1e6+100;
string str;
char s[N];
int main()
{
cin>>str;
int tp = 0; //栈顶
bool ans = true;
int n = str.length();
for(int i = 0; i<n; i++)
{
if(str[i] == '(' || str[i] == '[' || str[i] == '{')
s[tp++] = str[i];
else if(str[i] == ')')
{
if(!tp || s[tp-1] != '('){
ans = false;
break;
}
tp--;
}
else if(str[i] == ']')
{
if(!tp || s[tp-1] != '['){
ans = false;
break;
}
tp--;
}
else if(str[i] == '}')
{
if(!tp || s[tp-1] != '{'){
ans = false;
break;
}
tp--;
}
}
if(tp)
ans = false;
if(ans) puts("Yes");
else puts("No");
return 0;
}
C.子段乘积
链接：https://ac.nowcoder.com/acm/contest/3005/C
题目描述
给出一个长度为 n 的数列 a1,a2,…,an，求其长度为 k 的连续子段的乘积对 998244353 取模余数的最大值。
输入描述:
第一行两个整数n,k。 n≤200000,0≤ai ≤2^(30)−1
第二行n个整数
输出描述:
输出一个整数，代表最大余数。
尺取法，定义两个变量L和R，让R一直移动，若当前数字不为0，添加到res中去，当尺子(区间)的长度等于k时，更新答案，并让L向右移动一步，那res就需要除去L未移动前的那个位置上的值，因为题目要我们求的是乘积模998..的值，所以除法我们可以用乘法逆元转变成乘法，这里考虑的是没有遇到数字0，如果R遇到数字0，直接抛弃前面的区间，L = R+1，直接从0的下一个位置开始，继续移动尺子...
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 2e5+100, mod = 998244353;
typedef long long LL;
LL a[N];
LL ans,n,k;
LL qmi(LL a,LL k){
LL res = 1;
while(k){
if(k&1) res = res*a%mod;
k>>=1;
a = a*a%mod;
}
return res;
}
int main()
{
cin>>n>>k;
for(int i = 1; i<=n; i++) cin>>a[i];
LL l = 1, r = 1,res = 1;
for(; r<=n; ){
if(a[r] != 0){
res = res*a[r]%mod;
if((r-l+1)>=k) {
ans = max(ans,res);
res = res * qmi(a[l],mod-2)%mod;
l++; //向右移动一格
}
}else{
l = r+1;
res = 1;
}
r++;
}
cout<<ans<<endl;
return 0;
}
D.子段异或
链接：https://ac.nowcoder.com/acm/contest/3005/D
题目描述
输入一个数列a,你需要输出其中异或值为0的不同子段的数量。一个子段[l,r]的异或值为a(l) ^ a(l+1) ^ a(l+2) ^ ... ^ a(r)
两个子段被视为相同的，当且仅当其开始和结束位置均对应相同。
输入描述:
第一行一个整数 n ，代表数列长度。
第二行 n 个整数，代表数列。
输出描述:
输出一个整数，代表答案。
- ①[L,R]段的异或值：a(l) ^ a(l+1) ^ a(l+2) ^ ... ^ a(r)
- ②[1,L-1]段的异或值 ：a(1) ^ a(l+2) ^ ... ^ a(l-1)
- ③[1,R]段的异或值： a(1) ^ a(l+2) ^ ... ^ a(r-1) ^ a(r)
由上式可知，②^③ = ①，所以要使①为0，那么②^③ = 0，即S(L-1) = S(R),S数组是a数组的异或前缀，在遍历过程中用map维护即可
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;
const int N = 2e5+100;
typedef long long LL;
LL a[N],s[N];
LL ans,n;
map<LL,LL> h;
int main()
{
cin>>n;
for(int i = 1; i<=n; i++){
cin>>a[i];
s[i] = s[i-1] ^ a[i]; //异或前缀
if(s[i] == 0) ans ++; //[1,i]是答案，直接++
ans += h[s[i]];
h[s[i]] ++;
}
cout<<ans<<endl;
return 0;
}
E.最小表达式
链接：https://ac.nowcoder.com/acm/contest/3005/E
题目描述
给出一个包含数字1-9和加号的字符串，请你将字符串中的字符任意排列，但每种字符数目不变，使得结果是一个合法的表达式，而且表达式的值最小。输出那个最小表达式的值
合法的表达式的定义如下：
-
一个数字，如233，是一个合法的表达式
-
A + B是合法的表达式，当且仅当 A , B 都是合法的表达式
保证给出的表达式经过重排，存在一个合法的解。
输入描述:
一行输入一个字符串，仅包含数字1-9和加号+。
字符串的长度小于
输出描述:
一行输出一个数字，代表最小的解。
备注:
注意，答案长度可能长达500000个字符。
统计每个数字出现的次数，因为要我们求的是最小值，所以我们想让大的数放在权值低的地方,先把每个加数的个位填满，再填十位，百位...加数的数量比+号的数量多1，数字用完后，模拟一下十进制加法就行了(这里感叹一下，题解的代码实现真的很强，学习了)
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <string>
using namespace std;
const int N = 5e5+100;
typedef long long LL;
string s;
int a[N];
int cnt[10]; //存储每个数字的个数
int add; //记录＋号的个数，加数的个数=add+1
int main()
{
cin>>s;
int n = s.size();
for(int i = 0; i<n; i++){
if(s[i] == '+') add++;
else cnt[s[i]-'0'] ++;
}
add++; //加数的个数
int now = 0,t = 0;
//now代表当前的数字应该放到数字的哪一位
//t用来计数，当前操作的是哪一个加数
for(int i = 9; i>=1; i--){
while(cnt[i]){
a[now] += i;
cnt[i]--; //用掉了一个i
t = (t+1) % add;
if(!t) now ++; //所有数的个位累加完毕
//第一个t从0到add，a[now] = 9 + 9 + 8 + 8 + 7
//（23984692+238752+2+34+为例）=》2369+2359+248+248+237=5461
}
}
//模拟一下加法
for(int i = 0; i<N; i++){
a[i+1] = a[i+1] + a[i]/10; //进位
a[i] %=10;
}
//输出结果，从高位向低位输出
bool out = false;
for(int i = N; i>=0; i--){
if(out || a[i]){
cout<<a[i];
out =true;
}
}
return 0;
}
F.树上博弈
~
