第七届传智杯全国IT技能大赛程序设计赛道 国赛（总决赛）—— （B组）题解

1.小苯的木棍切割

【解析】首先我们先对数列排序，找到其中最小的数，那么我们就保证了对于任意一个第i+1个的值都会大于第i个的值那么第i+2个的值也比第i个大，那么我们第i+1次切木棍的时候一定会当第i个的值就变为了0的，第i+1减去的应该是第i个的值与第i-1个的差值，对于i+1到n同样如此，那么我们的递推关系就出来了，每次都切去的值都是（第i个跟第i-1个的差值）*（n-i+1)那么我们就可以用差分来写。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10; 
int t;
int a[N];
int b[N];
int main(){
cin>>t;
for(int i=0;i<t;i++){int n;cin>>n;memset(b,0,sizeof(b));memset(a,0,sizeof(a));for(int i=1;i<=n;i++){  cin>>a[i];}sort(a+1,a+n+1);for(int i=1;i<=n;i++){b[i]=a[i]-a[i-1];} long long max=0;//不开long long 见祖宗！！！for(int i=1;i<=n;i++){if(max<b[i]*(n-i+1)){max=b[i]*(n-i+1); } 	}cout<<max<<endl;
}	
}

2.大苯营

【解析】可以全部转化为等腰三角形来求解，我们经过观察得知当当x 和 y 的二进制没有任何交集时（即x&y=0 时）,x∣y=x⊕y。位运算来解。

#include<bits/stdc++.h>
using namespace std;
int main(){int n;cin>>n;while(n--){int x;cin>>x;int y=0;
//全部转化为2的30次方的操作for(int i = 30; i >= 0; i--) {if(x >> i & 1) {} else {y |= (1LL << i);}}if(y==0)cout<<-1<<endl;else cout<<y<<endl;}
}

3.小苯的排列数

【解析全排列题但是如果仅仅只是用dfs来进行全排列的话会超时。看题目范围，用dfs全枚举一边的时间是1!+2!+...+9!大概是4*10^5的时间复杂度。那么我们用dfs进行预处理，接着用二分以logn的复杂度来进行查找枚举。

#include<bits/stdc++.h>
using namespace std;
vector<int> v;
bool st[15];
int h=0;
int kk; 	
int l,r;
//dfs进行预处理
void dfs(int x,int y,int kk){
if(x==y){v.push_back(kk);return ;
}
for(int i=1;i<=y;i++){if(!st[i]){st[i]=true;dfs(x+1,y,kk*10+i);st[i]=false;	}
}	
}
//二分查找
void slove(){int lk=-1,rk=v.size();while(lk+1<rk){int mid=(lk+rk)/2;if(v[mid]<l)lk=mid;else rk=mid;	}if(v[lk]>=l&&v[lk]<=r)cout<<v[lk]<<endl;else if(v[rk]>=l&&v[rk]<=r)cout<<v[rk]<<endl;else cout<<-1<<endl;	
}
int main(){int t;cin>>t;for(int i=1;i<=9;i++)dfs(0,i,0);while(t--){cin>>l>>r;slove();}
}

4.小苯的字符串染色

【解析】

#include<bits/stdc++.h>
#define int long long
using namespace std;
void solve() {int n, k;cin >> n >> k;getchar();string str;getline(cin, str);
//取 k 和 n - k 中的较小值，因为找出包含 k 个 0 的子串和包含 n - k 个 1 的子串是等价的。k = min(k, n - k);int ret  = 0;for(int left = 0, right = 0, cnt = 0; right < n; right++) {if(str[right] == '1') cnt++;if(cnt < k) continue;while(cnt > k && left <= right) {if(str[left] == '1') cnt--;left++;}if(cnt == k) ret = max(ret, right - left + 1);}	for(int left = 0, right = 0, cnt = 0; right < n; right++) {if(str[right] == '0') cnt++;if(cnt < k) continue;while(cnt > k && left <= right) {if(str[left] == '0') cnt--;left++;}if(cnt == k) ret = max(ret, right - left + 1);}	cout << ret << "\n";
}
signed main() {int t ;cin >> t;while(t--) {solve();}
}

5.小苯的物理小球

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int>PII;#define fi first
#define se second
#define all(ss) ss.begin(),ss.end()
#define pb push_back
#define vi vector<int>
#define vii vector<vector<int>>
#define vl vector<LL>
#define vll vector<vector<LL>>
#define i128 __int128int const B=507;
double const eps=1e-6;
int const mod=998244353;
int const N=2e5+7,M=N*50;
int const INF=0x3f3f3f3f;
LL const INFF=0x3f3f3f3f3f3f3f3f;int n,m;
int x,y,z;
int ls[M],rs[M],tot,root;
LL sum[M],tag[M];void pushup(int u){sum[u]=sum[ls[u]]+sum[rs[u]];
}
void pushdown(int u,int l,int r){if(tag[u]==-1) return;if(ls[u]==0) ls[u]=++tot;if(rs[u]==0) rs[u]=++tot;int mid=(l+r)>>1;sum[ls[u]]=tag[u]*(mid-l+1);sum[rs[u]]=tag[u]*(r-mid);tag[ls[u]]=tag[u];tag[rs[u]]=tag[u];tag[u]=-1;
}
void modify(int &u,int l,int r,int x,int y,LL k){if(u==0) u=++tot;if(x<=l&&r<=y){sum[u]=k*(r-l+1);tag[u]=k; return;}pushdown(u,l,r);int mid=(l+r)>>1;if(mid>=x) modify(ls[u],l,mid,x,y,k);if(y>mid) modify(rs[u],mid+1,r,x,y,k);pushup(u);
}int query(int &u,int l,int r,int p){if(u==0) u=++tot;if(l==r){if(sum[u]==-1) sum[u]=r;	//没有初始化，则帮他初始化return sum[u];}pushdown(u,l,r);int mid=(l+r)>>1;if(mid>=p) return query(ls[u],l,mid,p);return query(rs[u],mid+1,r,p);
}LL qpow(LL a,LL b=mod-2,int p=mod){   //快速幂LL res=1%p;a%=p; 	//注意这个幂数b，不可以取模while(b){if(b&1)	res=res*a%p;a=a*a%p; b/=2;}return res;
}
/*
对线段高度从低到高考虑，每次计算当前线段的期望值
从小到大枚举高度，看当前线段的两端点会落在那里，
如果会落在更低的线段，直接转移过来，并且除2
如果会落在地方，就是用横坐标除2然后就是要维护x轴的每一个端点，直接开数组维护，空间时间都会爆
所以，我用的是动态开点线段树，维护值域
*/void solve(){scanf("%d%d",&n,&m);int mx=0;vector<array<int,3>>a;for(int i=0;i<n;i++){scanf("%d%d%d",&x,&y,&z);a.pb({z,x,y});mx=max(mx,x);mx=max(mx,y);}vector<array<int,2>>q;for(int i=0;i<m;i++){scanf("%d%d",&x,&y);q.pb({y,x});mx=max(mx,x);}sort(all(a));sort(all(q));LL ans=0;LL inv2=qpow(2);int j=0;for(int i=0;i<n;i++){//q[j]的高度更小while(j<m&&q[j][0]<a[i][0]){ //a数组无法影响d数组了int id=q[j][1];ans=(ans+query(root,1,mx,id))%mod;j++;}int x=a[i][1],y=a[i][2];	LL v1=query(root,1,mx,x);LL v2=query(root,1,mx,y);LL t=(v1+v2)*inv2%mod;if(x+1<=y-1&&y-1<=mx) modify(root,1,mx,x+1,y-1,t);}while(j<m){ 	//累加没有计算的int id=q[j][1];ans=(ans+query(root,1,mx,id))%mod;j++;}cout<<ans<<"\n";for(int i=0;i<=tot;i++) ls[i]=rs[i]=0,sum[i]=tag[i]=-1;root=tot=0;
}void init(){memset(tag,-1,sizeof tag);memset(sum,-1,sizeof sum);
}int main()
{init();int T;scanf("%d",&T);for(int i=1;i<=T;i++){solve();}return 0;
}

6.小苯的地下城寻宝

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,M=N*2,mod=998244353;
#define int long long
const long long inf=1e18;
const long long INF=1e18;
typedef pair<int,int> PII;
typedef long long LL;
using node=tuple<int,int,int>;
int n,m,k;
vector<int> coef(N,1);
vector<int> d[N];
void init(){coef[1]=0;for(int i=1;i<=100000;i++){for(int j=i;j<=100000;j+=i){d[j].push_back(i);if(j>i)coef[j]-=coef[i];}}
}
vector<int> g[N];
vector<int> dep[N];
int f[N],a[N];
int mx;
void dfs(int u,int fa,int depth){dep[depth].push_back(u);mx=max(mx,depth);for(auto v:g[u]){if(v!=fa){dfs(v,u,depth+1);}}
}
void solve()
{cin>>n;for(int i=1;i<=n;i++) g[i].clear(),dep[i].clear(),f[i]=0;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++){int x;cin>>x;if(x>0){g[i].push_back(x);g[x].push_back(i);}}mx=0;dfs(1,0,1);unordered_map<int,int>mp;f[1]=1;for(auto x:d[a[1]])mp[x]+=f[1];int res=1;for(int i=2;i<=mx;i++){for(auto v:dep[i]){for(auto x:d[a[v]]){f[v]=(f[v]+mp[x]*coef[x]%mod)%mod;f[v]=(f[v]%mod+mod)%mod;}res=(res+f[v])%mod;}for(auto v:dep[i]){for(auto x:d[a[v]]){mp[x]=(mp[x]+f[v])%mod;}}}cout<<res<<"\n";
}   signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;init();//  freopen("in.txt","r",stdin); //输入重定向，输入数据将从D盘根目录下的in.txt文件中读取 
//	freopen("out.txt","w",stdout); //输出重定向，输出数据将保存在D盘根目录下的out.txt文件中 cin>>t;while(t--) solve();
}