黑龙江大学程序设计竞赛（重现赛） 牛客网解题报告
这次的题解除了 f和j都有。。因为那俩我看一个是线段树一个是bit树有点搞不懂
话不多说 直接上题解了
a
题解：减掉前面没用的字符串 然后mod一下26
#include<bits/stdc++.h>
using namespace std;
#define maxn 200000+5
#define INF 0x3f3f3f3f
typedef long long int ll;
int main(){
int t,kase=1;
scanf("%d",&t);
while(t--){
int n;
//scanf("%d",&n);
n=kase++;
int tmp=1;
while(n>tmp)n-=tmp++;
n=(n-1)%26+1;
cout<<char(n-1+'a')<<endl;
}
return 0;
}
b
题解：这个把那个公式拆开就能发现 是所有(n-1)a(n)²的和减去2*a(n)*(a(n-1)*......a(1)) 用前缀和就行了
#include<bits/stdc++.h>
using namespace std;
#define maxn 200000+5
#define INF 0x3f3f3f3f
typedef long long int ll;
int a[maxn];
ll sum[maxn];
int main(){
int t;
scanf("%d",&t);
while(t--){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
sum[0]=0;
for(int i=1;i<=n;i++){
sum[i]=sum[i-1]+a[i];
}
ll ans=0;
for(int i=1;i<=n;i++){
ans+=1ll*(n-1)*a[i]*a[i];
}
for(int i=n;i>=1;i--){
ans-=2*a[i]*sum[i-1];
}
cout<<ans<<endl;
}
return 0;
}
c
题解：相邻的数互质
#include<bits/stdc++.h>
using namespace std;
#define maxn 200000+5
#define INF 0x3f3f3f3f
typedef long long int ll;
int main(){
int t,kase=1;
scanf("%d",&t);
while(t--){
int n;
scanf("%d",&n);
printf("%d\n",n);
}
return 0;
}
d：
题解：有点队列每次取出 时间最靠前的 如果这个工作没有机器能做 就放到队列里面去
如果有机器能做 就更新一下最后的时间
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <queue>
#define INF 0x3f3f3f3f
#define maxn 100000+5
using namespace std;
priority_queue<int,vector<int>,greater<int> >q;
struct node {
int l,r;
}a[maxn];
bool cmp(node x,node y){
if(x.l==y.l)return x.r<y.r;
else return x.l<y.l;
}
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d%d",&a[i].l,&a[i].r);
}
sort(a,a+n,cmp);
for(int i=0;i<n;i++){
int l=a[i].l,r=a[i].r;
if(q.empty()){
q.push(r);
}else {
int tmp=q.top();
q.pop();
//cout<<tmp<<endl;
if(l>=tmp){
tmp=r;
q.push(r);
}else{
q.push(r);
q.push(tmp);
}
}
}
cout<<q.size()<<endl;
return 0;
} d
题解：还以为这个题很难。。。。结果一下就水过了
从当前点往两边扩散就行了 求一下回文子串 这里的不同点在于绝对值的差是32就是相同的
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9+7;
typedef long long int ll;
#define maxn 500000+5
#define INF 0x3f3f3f3f
#define LLF 0x7fffffffffffffff
int main(){
string s;
cin>>s;
//cout<<'a'-'A'<<endl;
int n=s.size();
int ans=0;
for(int i=0;i<n;i++){
int flag=0;
for(int j=0;i-j>=0&&i+j+1<n;j++){
if(abs(s[i-j]-s[i+j+1])==32)
flag+=2;
else break;
}
ans=max(flag,ans);
}
cout<<ans<<endl;
}
g
题解：巴什博弈
#include<stdio.h>
#include <iostream>
using namespace std;
#define maxn 1000000+5
#define INF 0x3f3f3f3f
int main()
{
int t;
cin>>t;
while(t--){
int p,m;
cin>>p>>m;
if((p+m)%(m+1)==0)cout<<"Bob"<<endl;
else cout<<"Alice"<<endl;
}
return 0;
} h
题解：用两个数组标记一下行列（不能全染色，时间会爆）直接取一下行列的最大值就行
#include<stdio.h>
#include <iostream>
using namespace std;
#define maxn 1000000+5
#define INF 0x3f3f3f3f
int main()
{
int t;
cin>>t;
while(t--){
int p,m;
cin>>p>>m;
if((p+m)%(m+1)==0)cout<<"Bob"<<endl;
else cout<<"Alice"<<endl;
}
return 0;
} i
题解：既然要求两点的差值最小 那就用拓扑排序 然后更新一下dis
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9+7;
typedef long long int ll;
#define maxn 500000+5
#define INF 0x3f3f3f3f
#define LLF 0x7fffffffffffffff
vector<int>G[maxn],ans;
int ind[maxn];
ll dis[maxn];
void topo(){
queue<int>q;
q.push(1);
while(!q.empty()){
int tmp=q.front();
q.pop();
ans.push_back(tmp);
for(int i=0;i<G[tmp].size();i++){
int v=G[tmp][i];
ind[v]--;ll w=1ll*(tmp-v)*(tmp-v);
dis[v]=min(dis[v],dis[tmp]+w);
if(ind[v]==0){
q.push(v);
}
}
}
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
dis[i]=LLF;
}
dis[1]=0;
for(int i=1;i<=n;i++){
for(int j=2;j*i<=n;j++){
G[i].push_back(j*i);
//cout<<i<<" "<<j<<endl;
ind[(j*i)]++;
}
}
topo();
for(int i=1;i<=n;i++){
cout<<dis[i];
if(i!=n)cout<<" ";
else cout<<endl;
}
//for(int i=0;i<ans.size();i++){
// cout<<ans[i]<<" ";
//}
}
k
题解：从当前位置 每次往前借1
如果前面是0就0变成9再往前借
如果当前是 9就不借直接加上（我在说什么。。。感觉写麻烦了）
#include<bits/stdc++.h>
using namespace std;
#define maxn 200000+5
#define INF 0x3f3f3f3f
typedef long long int ll;
int a[maxn];
ll sum[maxn];
int main(){
//#ifndef ONLINE_JUDGE //if not define 如果没有定义这个的话就执行下面
///freopen("input.txt", "r", stdin); //只改变输入流的文件指针，读入这个文件的内容（必须要有input这个文件）stdin是标准输入流的文件指针
//freopen("output1.txt", "w", stdout); //只改变输出流的文件指针，写入output内（如果没有output这个文件就会自动生成）stdout是标准输出流的文件指针
//#endif
int t;
scanf("%d",&t);
while(t--){
string s;
cin>>s;
string n=s;
int ans=0;
for(int i=s.size()-1;i>=0;i--){
int tmp=s[i]-'0';
if(i-1>=0&&s[i-1]-'0'!=0&&s[i]!='9'){
ans+=tmp+10;
s[i-1]--;
}
else if(i-1>=0&&s[i-1]=='0'&&s[i]!='9'){
ans+=tmp+10;
int j=i-1;
while(s[j]=='0'){
ans+=9;
j--;
}
s[j]--;
i=j+1;
}else ans+=tmp;
}
cout<<ans<<endl;
//cout<<"n="<<n<<":"<<ans<<endl;
}
return 0;
}
诺瓦星云工作强度 18人发布
投递影石Insta360等公司10个岗位 >