大连大学2022年4月4月程序设计竞赛题解
Solution A(数据泄露):
因为数据范围只有500，且可能包含重边、自环和不连通，所以很容易想到flyod算法。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
ll num[1005][1005];
int main(){
ll n,m;
cin>>n>>m;
memset(num,0x3f,sizeof num);
for(int i=1;i<=n;i++){
num[i][i]=0;
}
for(int i=0;i<m;i++){
ll a,b,s;
cin>>a>>b>>s;
num[a][b]=min(num[a][b],s);
num[b][a]=min(num[b][a],s);
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(num[i][k]<1e9&&num[k][j]<0x3f3f3f3f){
num[i][j]=min(num[i][j],num[i][k]+num[k][j]);
}
}
}
}
int k;
cin>>k;
int start=1;
ll re=0;
for(int i=0;i<k;i++){
int p;
cin>>p;
if(re==-1) continue;
if(num[start][p]>1e9){
re=-1;
continue;
}
re+=num[start][p];
start=p;
}
cout<<re<<endl;
return 0;
}
Solution B(波格丹危机):
签到题，按照题意排序即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
int main(){
int n;
cin>>n;
vector<pair<int,string>> v;
while(n--){
string s;
int a;
cin>>s>>a;
v.push_back({a,s});
}
sort(v.begin(),v.end());
for(int i=0;i<v.size();i++){
if(v[i].second=="."||v[i].second=="!") cout<<v[i].second<<endl;
else cout<<v[i].second<<" ";
}
return 0;
} Solution C(末日将至):
首先，如果发生全反射，说明一定能照射到全部数据包。
如果不能，当光照射在两个挡板交界处时，我们需要判断是否有数据包在光上面。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
int main(){
int T;
cin>>T;
while(T--){
int a,b,n;
double k;
cin>>a>>b>>n>>k;
pair<int,int> nums[n];
for(int i=0;i<n;i++){
cin>>nums[i].first>>nums[i].second;
}
double tana=(double)b/(double)a;
double ana=atan(tana);
double sina=sin(ana);
double sinb=sina/k;
bool c=0;
if(fabs(sinb-1.0)>0.000001&&sinb>1.0){
c=1;
}
if(c==1){
cout<<"YES"<<endl;
continue;
}
double k2=tan(asin(sinb));
double b2=b-k2*a;
bool f=1;
for(int i=0;i<n;i++){
double y1=k2*nums[i].first+b2;
if(fabs(nums[i].second-y1)>0.000001&&nums[i].second>y1){
f=0;
}
}
if(f==1) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
} Solution D(Raksasa的摸der):
本题考虑对多种情况的判断。
例如：d ，de 会对后面的r的贡献产生影响。算区间的时候不能把前面的d，de考虑进去。
解题思路是按照多种情况考虑，算清楚所有情况即可。运用前缀和计数。
#include <bits/stdc++.h>
using namespace std;
#define inf 0x7ffffffffffffff
#define N 1005000
#define mod 1000000007
#define mod2 998244353
#define ll long long
char c[N];
ll der[N][3],er[N][2],r[N];
int main()
{
ll n,x;
scanf("%lld%lld",&n,&x);
scanf("%s",c+1);
ll ans=0;
for(int i=1; i<=n; i++)
{
if(c[i]=='d')
{
der[i][0]=der[i-1][0]+1;
der[i][1]=der[i-1][1];
der[i][2]=der[i-1][2];
er[i][0]=er[i-1][0];
er[i][1]=er[i-1][1];
r[i]=r[i-1];
}
else if(c[i]=='e')
{
der[i][0]=der[i-1][0];
der[i][1]=der[i-1][1]+der[i-1][0];
der[i][2]=der[i-1][2];
er[i][0]=er[i-1][0]+1;
er[i][1]=er[i-1][1];
r[i]=r[i-1];
}
else if(c[i]=='r')
{
der[i][0]=der[i-1][0];
der[i][1]=der[i-1][1];
der[i][2]=der[i-1][2]+der[i-1][1];
er[i][0]=er[i-1][0];
er[i][1]=er[i-1][0]+er[i-1][1];
r[i]=r[i-1]+1;
}
else
{
der[i][0]=der[i-1][0];
der[i][1]=der[i-1][1];
der[i][2]=der[i-1][2];
er[i][0]=er[i-1][0];
er[i][1]=er[i-1][1];
r[i]=r[i-1];
}
}
for(int i=x;i<=n;i++)
{
ans=max(ans,der[i][2]-der[i-x][2]-der[i-x][0]*(er[i][1]-er[i-x][1]-er[i-x][0]*(r[i]-r[i-x]))-der[i-x][1]*(r[i]-r[i-x]));
}
printf("%lld\n",ans);
return 0;
} 也可以按区间一位一位算，这里给出验题人（Cantor.）的代码
#include<bits/stdc++.h>
#define oo 0x3f3f3f3f
#define OO 0x3f3f3f3f3f3f3f3f
#define LL long long
#define sz(x) int(x.size())
#define PII pair<int,int>
#define VI vector<int>
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define STP system("pause")
using namespace std;
const int N=1e6;
void Solve(){
int n,m;
string s;
cin>>n>>m>>s;
vector<LL> f(6);
//f0 = 'd' f1 = 'e' f2 = 'r' f3 = 'de' f4 = 'er' f5 = 'der'
auto Add=[&](char x){
if(x=='d') f[0]+=1;
if(x=='e') f[1]+=1,f[3]+=f[0];
if(x=='r') f[2]+=1,f[4]+=f[1],f[5]+=f[3];
};
auto Delete=[&](char x){
if(x=='d') f[0]-=1,f[3]-=f[1],f[5]-=f[4];
if(x=='e') f[1]-=1,f[4]-=f[2];
if(x=='r') f[2]-=1;
};
auto Print=[&](){
for(int i=0;i<6;++i)
cout<<f[i]<<" \n"[i==5];
};
for(int i=0;i<m;++i){
Add(s[i]);
}
LL ans=f[5];
for(int i=m;i<n;++i){
Delete(s[i-m]);
Add(s[i]);
ans=max(ans,f[5]);
}
cout<<ans<<'\n';
}
int main(){
Solve();
} Solution E(数圆圈):
对于任意1e18以内的数，我们迭代几十次以后都会变成0-1-0-1的循环。
所以我们迭代出0或1以后直接算就可以了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
ll f(ll num){
string s=to_string(num);
ll re=0;
for(int i=0;i<s.size();i++){
if(s[i]=='6'||s[i]=='9'||s[i]=='0')re++;
if(s[i]=='8')re+=2;
}
return re;
}
int main() {
int T;
cin>>T;
while(T--){
ll n,k;
cin>>n>>k;
ll re=n;
while(k){
re=f(re);
k--;
if(re==0||re==1) break;
}
if(k%2==1){
if(re==0) re=1;
else re=0;
}
cout<<re<<endl;
}
return 0;
} solution F(旅行):
考虑一个点在1-n某一条最短路径的条件，我们设dis(i,j)表示i到j的最短路径，如果点x在1-n的最短路径上，那么一定有dis(1,x)+dis(x,n)=dis(1,n)，考虑到数据只有只有10^3级别，所以我们可以从1-n每个点出发跑一遍堆优化dijkstra，对于输入的x直接判断,时间复杂度O((n+m)^2log(n+m)+m)。
题解采用了另外一种做法。先正常建边以1号点为起点跑堆优化dijkstra，得到1到其他点的最短路径数组dis，然后建一张反图(如果存在边a->b，在反图中存在边b->a)，以n号点为起点跑堆优化dijkstra，得到n到其他点的最短路径数组dis1，则对于输入的x，我们直接判断dis(1,x)+dis1(n,x)是否等于dis(1,n)即可，时间复杂度O((n+m)log(n+m)+m)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define INF 2147483647
#define N 100005
#define M 200005
using namespace std ;
struct Edge { int nxt,to,dist ; } e[M],e1[M] ;
struct node {
int id,d ;
bool operator <(const node &a) const {
return d>a.d ;
}
};
int head[N],head1[N],tot1=0,tot=0 ;
int n,m,S ;
int dis[N],dis1[N] ;
bool vis[N] ;
priority_queue<node> q ;
inline void add(int from,int to,int dist) {
e[++tot].to=to ; e[tot].dist=dist ;
e[tot].nxt=head[from] ; head[from]=tot ;
}
inline void add1(int from,int to,int dist) {
e1[++tot1].to=to ; e1[tot1].dist=dist ;
e1[tot1].nxt=head1[from] ; head1[from]=tot1 ;
}
void dijkstra(int S) {
fill(vis+1,vis+n+1,0) ;
fill(dis+1,dis+n+1,INF) ;
dis[S]=0 ; q.push((node){S,0}) ;
while(!q.empty()) {
node x=q.top() ; q.pop() ;
if(vis[x.id]) continue ;
vis[x.id]=1 ;
for(int i=head[x.id];i;i=e[i].nxt) {
int y=e[i].to ;
if(dis[y]>dis[x.id]+e[i].dist) {
dis[y]=dis[x.id]+e[i].dist ;
if(!vis[y]) q.push((node){y,dis[y]}) ;
}
}
}
}
void dijkstra1(int S) {
fill(vis+1,vis+n+1,0) ;
fill(dis1+1,dis1+n+1,INF) ;
dis1[S]=0 ; q.push((node){S,0}) ;
while(!q.empty()) {
node x=q.top() ; q.pop() ;
if(vis[x.id]) continue ;
vis[x.id]=1 ;
for(int i=head1[x.id];i;i=e1[i].nxt) {
int y=e1[i].to ;
if(dis1[y]>dis1[x.id]+e1[i].dist) {
dis1[y]=dis1[x.id]+e1[i].dist ;
if(!vis[y]) q.push((node){y,dis1[y]}) ;
}
}
}
}
int main() {
scanf("%d%d%d",&n,&m,&S) ;
for(int i=1,u,v,w;i<=m;++i) {
scanf("%d%d%d",&u,&v,&w) ;
add(u,v,w) ; add1(v,u,w) ;
}
dijkstra(1) ;
dijkstra1(n) ;
while(S--)
{
int x ;
scanf("%d",&x) ;
if(1LL*dis[x]+dis1[x]==1LL*dis[n])
printf("yes\n") ;
else printf("no\n") ;
}
return 0 ;
} Solution G(全体目光看向我，我宣布个事):
单纯的统计，实在不行也可以开26个变量来计数。
#include <bits/stdc++.h>
using namespace std;
#define inf 0x7ffffffffffffff
#define N 1005000
#define mod 1000000007
#define mod2 998244353
#define ll long long
ll buc[N];
int main()
{
ll n;
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
char ch;
scanf(" %c",&ch);
buc[ch]++;
}
ll ans=0;
char ch;
for(int i='A';i<='Z';i++)
{
if(ans<buc[i])
{
ans=buc[i];
ch=i;
}
}
printf("%c",ch);
return 0;
}
Solution H(寻找最大差值):
我们创建两个数组，第一个数组是从下标0到i的最小值，第二个数组是从最后面到i的最大值。
然后遍历这两个数组，使用最大值减去最小值即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
int main(){
int T;
cin>>T;
while(T--){
int n;
cin>>n;
int num[n];
for(int i=0;i<n;i++){
cin>>num[i];
}
deque<int> mx;
deque<int> mi;
for(int i=0;i<n;i++){
if(i==0) mi.push_back(num[0]);
else{
mi.push_back(min(mi.back(),num[i]));
}
}
for(int i=n-1;i>=0;i--){
if(i==n-1) mx.push_front(num[n-1]);
else mx.push_front(max(num[i],mx.front()));
}
int re=-1;
for(int i=0;i<n;i++){
if(mx[i]>mi[i])re=max(re,mx[i]-mi[i]);
}
cout<<re<<endl;
}
return 0;
} 另一份代码：
#include <bits/stdc++.h>
using namespace std;
#define inf 0x7ffffffffffffff
#define N 1005000
#define mod 1000000007
#define mod2 998244353
#define ll long long
ll a[N];
int main()
{
ll t;
scanf("%lld",&t);
while(t--)
{
ll n;
scanf("%lld",&n);
ll num=0;
ll ans=-1;
for(int i=0;i<n;i++) scanf("%lld",&a[i]);
for(int i=n-1; i>=0; i--)
{
num=max(a[i],num);
if(num-a[i]>0) ans=max(num-a[i],ans);
}
printf("%lld\n",ans);
}
return 0;
} solution I(彩虹) :
7种颜色染格子，要求相邻格子颜色不相同，求染色的方案数。
经典状压dp。
我们令dp(i,j)表示第i行状态为j的染色方案数，其中状态j模拟一个n位7进制数，第k位为0-6分别代表格子(i,k)上的颜色为第1-7种颜色，则有dp转移方程
$$
但是本题要注意处理一下一行的合法颜色，不然会TLE
#include<bits/stdc++.h>
#define N 65536
#define mod 1000000007
#define LL long long
using namespace std ;
int q[N],n,m,num=0 ;
LL f[15][N] ;
bool check(int len,int x,int y)
{
int s,t ;
while(len--)
{
s=x%7,t=y%7 ;
if(s==t) return false ;
x/=7 ; y/=7 ;
}
return true ;
}
int main()
{
cin>>n>>m ;
int res=1 ;
for(int i=1;i<=n;++i) res*=7 ;
for(int i=0;i<res;++i)
{
int len=n,s=i/7,lst=i%7 ;
bool flag=1 ;
while(--len)
{
if(s%7==lst)
{
flag=0 ;
break ;
}
lst=s%7 ; s/=7 ;
}
if(flag) q[++num]=i ;
}
memset(f,0,sizeof(f)) ;
for(int i=1;i<=num;++i) f[1][i]=1 ;
for(int i=2;i<=m;++i)
{
for(int j=1;j<=num;j++)
for(int k=1;k<=num;++k)
if(check(n,q[j],q[k]))
f[i][j]=(f[i][j]+f[i-1][k])%mod ;
}
LL ans=0 ;
for(int i=1;i<=num;++i)
ans=(ans+f[m][i])%mod ;
cout<<ans<<endl ;
return 0 ;
} Solution J(突然的自我):
签到题，根据题意，很容易推出f(i)=f(i-1)+f(i-2)+1。
Solution K(Raksasa的轻功):
因为跳法的原因，可以判断出具有传递性。
提供两种思路：
一种是判断高低，记录每一座山峰往左和往右能跳到的最低山峰位置
#include <bits/stdc++.h>
using namespace std;
#define inf 0x7ffffffffffffff
#define N 1005000
#define mod 1000000007
#define mod2 998244353
#define ll long long
ll a[N];
ll pre[N],suf[N];
int main()
{
ll n;
scanf("%lld",&n);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
ll mark=1;
for(int i=1;i<=n;i++)
{
if(a[i]>a[i-1]) pre[i]=mark;
else pre[i]=mark=i;
}
mark=n;
for(int i=n;i>=1;i--)
{
if(a[i]>a[i+1]) suf[i]=mark;
else suf[i]=mark=i;
}
ll ans=0;
for(int i=1;i<=n;i++) ans=max({ans,i-pre[i],suf[i]-i});
printf("%lld\n",ans);
return 0;
}
另一种是直接从左跑到右，从右跑到左，各跑一遍。
#include <bits/stdc++.h>
using namespace std;
#define inf 0x7ffffffffffffff
#define N 1005000
#define mod 1000000007
#define mod2 998244353
#define ll long long
ll a[N];
int main()
{
ll n;
scanf("%lld",&n);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
ll up=0,down=0;
ll ans=0;
for(int i=1;i<n;i++)
{
if(a[i]<a[i+1])
{
up++;
down=0;
}
else if(a[i]>a[i+1])
{
down++;
up=0;
}
else
{
up=0;
down=0;
}
ans=max({ans,up,down});
}
printf("%lld\n",ans);
return 0;
} solution L(函数求和):
一句话题意:
$$
所以
$$
直接求和取模即可，时间复杂度O(m)
#include<bits/stdc++.h>
#define N 10000005
#define mod 1000000007
#define LL long long
using namespace std ;
int a[N],c[N],n,m ;
inline void read(int &num)
{
int s = 0 ; char ch = getchar();
while(ch < '0' || ch > '9') ch = getchar();
while(ch >= '0' && ch <= '9') s = (s<<3) + (s<<1) + ch - '0', ch = getchar();
num = s;
}//快读，可以用scanf代替
int main() {
int n,m ;
read(n),read(m) ;
for(int i=1;i<=n;++i) read(a[i]) ;
LL ans=0 ; int x ;
while(m--)
{
read(x) ; LL res ;
if(x==a[x]) res=x ;
else res=1 ;
ans=(ans+res)%mod ;
}
printf("%lld\n",ans) ;
return 0 ;
} Solution M(Raksasa的棋局):
本题可以预处理出馬踩的所有的位置最快需要多少步（bfs），将其存储在数组中，O(1)查询即可
#include <bits/stdc++.h>
using namespace std;
#define inf 0x7ffffffffffffff
#define N 1010
#define mod 1000000007
#define mod2 998244353
#define ll long long
ll dp[N][N];
ll dx[8]={1,2,2,1,-1,-2,-2,-1};
ll dy[8]={-2,-1,1,2,-2,-1,1,2};//馬的8个走向
int main()
{
ll n,m,q;
scanf("%lld%lld%lld",&n,&m,&q);
ll x1,y1;
scanf("%lld%lld",&x1,&y1);
queue<pair<ll,ll>> qu;
qu.push({x1,y1});
while(!qu.empty())
{
pair<ll,ll> pa=qu.front();
qu.pop();
for(int i=0;i<8;i++)
{
ll x=pa.first+dx[i];
ll y=pa.second+dy[i];
if(x==x1&&y==y1) continue;
if(x<1||x>n||y<1||y>m) continue;
if(!dp[x][y])
{
dp[x][y]=dp[pa.first][pa.second]+1;
qu.push({x,y});
}
}
}
while(q--)
{
ll x,y;
scanf("%lld%lld",&x,&y);
if(dp[x][y]) printf("%lld\n",dp[x][y]);
else printf("-1\n");
}
return 0;
}
Solution N(Raksasa的数字):
把数组中每一个数字都转换成二进制，异或1会把数字“翻转”
例如： 1 异或 1为0，0异或 1 为 1。
统计每一位（转换成二进制）上有多少个1和0，因为异或1会把所有的1变成0,0变成1。所有就等同于1和0的数目交换。所有就算一下性价比，尽量往小的换即可。
#include <bits/stdc++.h>
using namespace std;
#define inf 0x7ffffffffffffff
#define N 1005000
#define mod 1000000007
#define mod2 998244353
#define ll long long
vector<bitset<32>> ve;
ll cnt[32];
int main()
{
ll t;
scanf("%lld",&t);
while(t--)
{
ll n;
ve.clear();
scanf("%lld",&n);
for(int i=0;i<n;i++)
{
ll x;
scanf("%lld",&x);
bitset<32> bi(x);
ve.push_back(bi);
}
memset(cnt,0,sizeof(cnt));
for(int i=0;i<n;i++)
{
for(int j=0;j<32;j++)
{
if(ve[i][j]) cnt[j]++;
}
}
ll ans=0;
for(int i=0;i<32;i++)
{
if(cnt[i]>n/2)
{
ans+=(1ll<<i);
}
}
printf("%lld\n",ans);
}
return 0;
}
投递中国农业发展银行等公司10个岗位 >
