寒假训练赛4 子段异或 mod 双指针 栈
本次训练赛大量涉及STL。
D题
题意
https://ac.nowcoder.com/acm/contest/3005/D
长度为n数组，求子段异或值为0的个数。
这道题据说是滴滴还是字节跳动面试题改编，原题是不可分割求最大，用DP，这一题是可分割，应该是简单了不少。
思路
与其说思路不如说是教训。
- 数组开太大（2e5*2e5）即使是在全局变量里面开出来也不允许，而且这种情况是段错误而不是MLE。
- wa了也不能证明不会TLE。
- N=2e5就不要幻想n2的复杂度能过了。
我的错误代码
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int N=2e5+7;
ll a[N],res[N];
int main() {
int n;
cin>>n>>a[1];
res[1]=a[1];
ll cnt=0;
for(int i=2; i<=n; i++) {
cin>>a[i];
res[i]=res[i-1]^a[i];
if(!res[i]) cnt++;
}
for(int i=2; i<=n; i++) {
for(int j=i; j<=n; j++) {
res[j]=res[j]^res[i-1];
if(!res[j]) cnt++;
}
}
cout<<cnt<<endl;
return 0;
}//通过率60% TLE出题人的正确思路
作者：nocriz https://ac.nowcoder.com/discuss/365889?toCommentId=5266036
如果[l,r]是合法的子段，说明前缀和中xorsum[r]^xorsum[l-1] = 0, xorsum[l-1] = xorsum[r]。
求出异或前缀和，然后使用map计数每一个数字有多少个前缀和等于那个数字即可。
出题人太强了，本菜鸡没看懂，只能自己琢磨一下：
我写了一个生成前缀和xorsum的程序来辅助理解
#include<bits/stdc++.h>
using namespace std;
int main() {
int n,k,y=0;
cin>>n;
int xorsum[10]= {0};
for(int i=1; i<=n; i++)
cin>>k,xorsum[i]=xorsum[i-1]^k,cout<<xorsum[i]<<" ";
}
/* 输入输出：
5
1 2 3 2 1
1 3 0 2 3 */如果[l,r]是合法子段 xorsum[r]^xorsum[l-1] = 0
我明白了，就是我的方案的终极优化版。
正确代码
#include<iostream>
#include<map>
using namespace std;
map<int,int> mp;
int main(){
int n,k,y=0;
cin>>n;
long long sum=0;
mp[0]++;
while(n--){
cin>>k;//不用存的gjr
y^=k;
sum+=mp[y];//前面有多少个相同的前缀和就加多少个
mp[y]++;//本身记录
}
cout<<sum<<endl;
}E题
题意
https://ac.nowcoder.com/acm/contest/3005/E
将字符串中的字符任意排列，但每种字符数目不变，使得结果是一个合法的表达式，而且表达式的值最小。输出结果。
思路
有多少个加号就有多少个区间，把所有的数字放在一起sort，因为不包括0，所以直接从小到大往高位放就是了。
然后就是一个字符串模拟大数加法，可以拿之前的大数类模板来试试手。
等我有空（）回来补一下吧。
代码
cpp代码
#include<iostream>
#include<algorithm>
using namespace std;
int tail,head;
int s[500005],c;
int ans[500005],jw=0,pl;
int main() {
while((c=getchar())!='\n') {
if(c=='+')
pl++;
else
s[++tail]=c-'0';
}
pl++;
sort(s,s+tail+1);
for(int i=tail; i>=1; i-=pl) {
int base=0;
for(int j=i; j>=i-pl+1&&j>=1; j--) {
base+=s[j];
}
base+=jw;
ans[++head]=base%10;
jw=base/10;
}
if(jw>0)
ans[++head]=jw;
for(int i=head; i>=1; i--)
printf("%d",ans[i]);
return 0;
}Python代码
s=input()
num=1
List=[0]*10
for i in s:
if i=='+':
num+=1
else:
List[int(i)]+=1
Sum=0
ans=[]
Len=len(s)-num+1
def fun():
global List
for i in range(9,0,-1):
if List[i]>0:
List[i]-=1
return i
else:
return 0
for i in range(Len):
if i%num==0:
ans.append(str(Sum%10))
Sum//=10
Sum+=fun()
print(str(Sum)+''.join(ans[:0:-1]))
# 我还以为可以直接大数处理呢 C题
思路
划分区间，双指针。除法要记得取模！！！
代码
本菜鸡的代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=998244353;
const int N=2e5+7;
ll a[N];
int pos[N];
ll qkpow(ll x, ll y) {
ll ans = 1;
x = x % mod;
while (y) {
if(y&1) ans = ans * x % mod;
x = x * x % mod;
y =y >>1;
}
return ans;
}
ll getInv(ll x) {
return qkpow(x,mod-2);
}
int main() {
int n,k,t=1;
cin>>n>>k;
for(int i=1; i<=n; i++) {
cin>>a[i];
if(a[i]==0) pos[t++]=i;
}
int right[N],left[N],as=0,it;
for(it=1; it<t; it++)
if(pos[it]-pos[it-1]>k) right[as]=pos[it]-1,left[as++]=pos[it-1]+1;
//共有0 - as-1 段 区间右端点分别为right
if(n-k>=pos[t-1]) left[as]=pos[t-1]+1,right[as++]=n;
ll ans=0;
for(int j=0; j<as; j++) {
int L=left[j],R=right[j];
//cout<<"L="<<L<<" R="<<R<<endl;
ll tmp=1;
for(int i=L; i<L+k; i++) {
tmp*=a[i];
tmp%=mod;
}
ans=max(ans,tmp);
for(int i=L+k; i<=R; i++) {
tmp=tmp*getInv(a[i-k]);
tmp%=mod;
tmp*=a[i];
tmp%=mod;
ans=max(ans,tmp);
}
}
cout<<ans<<endl;
return 0;
}更加简单干净的表述
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
const ll mod=998244353;
ll p[200005];
int n,k;
ll qm(ll x,ll y){
ll ans=1;
while(y){
if(y&1) ans=ans*x%mod;
x=x*x%mod;
y>>=1;
}
return ans;
}
int main(){
cin>>n>>k;
ll ans=0;
ll cnt=1;
int num=0;
for(int i=1;i<=n;i++){
cin>>p[i];
if(p[i]==0){
num=0;
cnt=1;
}
else{
num++;
cnt=cnt*p[i]%mod;
if(num==k){
ans=max(ans,cnt);
cnt=cnt*qm(p[i-k+1],mod-2)%mod;
num--;
}
}
}
cout<<ans;
}Python代码
n,k=map(int,input().split())
a=list(map(int,input().split()))
S=1
num=ans=0
p=998244353
for i in range(n):
if a[i]:
S*=a[i]
num+=1
if num>k:
S*=pow(a[i-k],p-2,p)
num-=1
if num==k:
ans=max(ans,S%p)
else:S=1;num=0
S%=p
print(ans)B题
思路
看了半天都没看出来是栈，想了很久……
代码
我的
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
bool chk(string s) {
char stack [s.length()];
int head = 0;
for(int i=0;i<s.length();i++) {
char c=s[i];
switch(c) {
case '{':
case '[':
case '(':
stack[head++] = c;
break;
case '}':
if(head == 0 || stack[--head] != '{') return false;
break;
case ')':
if(head == 0 || stack[--head] != '(') return false;
break;
case ']':
if(head == 0 || stack[--head] != '[') return false;
break;
}
}
return head == 0;
}
int main() {
string s;
cin>>s;
if(chk(s)) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
return 0;
}STL
#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;
int main() {
string s;
cin>>s;
int n=s.length();
stack <char> st;
for(int i=0;i<n;i++){
if(s[i]=='('||s[i]=='['||s[i]=='{') st.push(s[i]);
else if(s[i]==')'&&!st.empty()&&st.top()=='(') st.pop();
else if(s[i]==']'&&!st.empty()&&st.top()=='[') st.pop();
else if(s[i]=='}'&&!st.empty()&&st.top()=='{') st.pop();
else {
cout<<"No"<<endl;
return 0;
}
}
if(st.empty()) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
return 0;
}- st.pop要加非空判断 如果空 会越界 RE
- 对于string s.size()和s.length()都可以
Python
s=input() S=[] for i in s: S.append(i) if len(S)>1 and S[-2:] in(['(',')'],['[',']'],['{','}']): S.pop();S.pop() print('YNeos'[S!=[]::2])stl
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main(){ string s; stack<char>a; cin>>s; for(int i=0;i<s.size();i++){ if(!a.empty()&&((s[i]==')'&&a.top()=='(')||(s[i]==']'&&a.top()=='[')||(s[i]=='}'&&a.top()=='{'))) a.pop(); else a.push(s[i]); } if(!a.empty()) puts("No"); else puts("Yes"); }最后A题错了两次因为没改longlong
