ACM训练日记—4月28日(北京师范大学第十六届程序设计竞赛决赛-重现赛)

本文主要是介绍ACM训练日记—4月28日(北京师范大学第十六届程序设计竞赛决赛-重现赛)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

还是继续整理下题目。

A—塞特斯玛斯塔

签到水题

B—外挂使用拒绝

题意：
当他把一个账号的金钱转移到另一个账户时，原来账户里的金钱并不会减少！一共有n个账号，把第1个账号的金钱“转移”到第2个账号，再把第2个账号的金钱“转移”到第3个账号，……，再把第n-1个账号的金钱“转移”到第n个账号。每当一个账号的金钱数大于等于1000000007(=109+7)时，这个账号的金钱数就会对109+7取模，即变成金钱数除以109+7的余数。将三七开的所有账号的金钱数恢复至他开挂以前的数值。只有现在的金钱数的数据，以及检测到的开挂天数k。n(2 ≤ n ≤ 1000),k(0 ≤ k ≤ 100000000)

思维题，利用dp推出矩阵，找到其中矩阵快速幂的规律，在找到矩阵相乘k次后的规律。具体还是推荐看下面一位大佬的讲解吧。

来自：https://blog.csdn.net/hnust_Derker/article/details/79831869

dp[k][1]=dp[k−1][1]
dp[k][2]=dp[k−1][2]+dp[k][1]
.....
dp[k][n]=dp[k][n-1]+dp[k-1][n]
推出
dp[k−1][1]=dp[k][1]
dp[k−1][2]=dp[k][2]−dp[k][1]
.....
dp[k-1][n]=dp[k][n]-dp[k][n-1]

即，得矩阵
[dp[0][1]]=[1,0,0...0]^k [dp[k][1]]
[dp[0][2]]=[-1,1,0..0] [dp[k][2]]
[dp[0][3]]=[0,-1,1..0] [dp[k][3]]
... ...
[dp[0][n]]=[0,0,.-1,1] [dp[k][n]]
这个东西本来是矩阵快速幂解决，但是nn到了10001000，这样的话时间就是O(n3logk)O(n3log⁡k)，
显然不行，那就打个表出来，发现了......这个矩阵kk次幂之后A[i][j]A[i][j] = (−1)^(i−j)∗C(k,i-j)，
这样从(i,i)(这个位置往前推，但是组合数很大，注意C(k,x)可以由Cx−1kCkx−1递推而来。)

代码来自：https://blog.csdn.net/hnust_Derker/article/details/79831869

#include<bits/stdc++.h>
typedef long long ll;
const int maxn = 1e3 + 10;
const ll mod = 1e9 + 7;
using namespace std;
ll n, m, T, kase = 1, k;
ll ans[maxn], a[maxn], inv[maxn];
ll qmod(ll x, ll n, ll mod) {
ll ans = 1;
for( ; n; n >>= 1) {
if(n & 1) ans = ans * x % mod;
x = x * x % mod;
}
return ans;
}
int main() {

for(ll i = 1; i < maxn; i++) inv[i] = qmod(i, mod - 2, mod);
scanf("%d", &T);
while(T--){
scanf("%lld %lld", &n, &k);
for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
for(int i = 1; i <= n; i++) {
ll now = 1; ans[i] = a[i];
for(int j = i - 1; j >= 1; j--) {
int flag = (i - j) & 1;
int res = (i - j);
now = now * inv[res] % mod;
now = now * (k - res + 1) % mod;
if(flag) ans[i] -= now * a[j];
else ans[i] += now * a[j];
ans[i] %= mod;
}
}
for(int i = 1; i <= n; i++) {
if(ans[i] < 0) ans[i] +=mod;
printf("%lld%c", ans[i], i < n ? ' ' : '\n');
}
}
return 0;
}

C—萌萌哒身高差

题意：给出一个数n，找出1,2...n的全排列，对于每一个排列，相邻两位数差的绝对值之和。

打表找规律可以发现ans=((n^2)-1)/3;

至于严格证明官方给出题解有解释，，，，我没怎么弄明白。

官方题解：枚举贡献， ans = (1/n!)∑( i=1:n)∑(j=1:n) abs(i−j)×(n−1)×(n−2)!，化简得

ans = (1/ n)∑(i=1:n)∑ (j=1:n)abs(i−j)，复杂度 O(n2)。

D—雷电爆裂之力

南北方向有四条马路，从西到东依次是京师路，木铎路，金声路和新街口外大街，
可以看成是四条平行的数轴，且相邻的两条数轴之间距离为1m。东西走向有许多小道连接了相邻的马路。
现在zhuaiballl位于京师路的某个位置，想要出发前往新街口外大街，
速度为1m/s。由于可能没有一条路径从西到东一直连向新街口外大街，所以每次遇到丁字路口时，
zhuaiballl需要选择是往左走还是往右走

我是用贪心的想法，加上二分，复杂度(n(log n)^2).

代码：

ll a[100005],b[100005],c[100005];
ll n,m,k;
ll solve1(ll val)
{
ll l=1,r=m;
while(l<=r)
{
ll mid=(l+r)/2;
if(mid==val) return mid;
else if(b[mid]<val) l=mid+1;
else r=mid-1;
}
return r;
}
ll solve2(ll val)
{
ll l=1,r=k;
while(l<=r)
{
ll mid=(l+r)/2;
if(mid==val) return mid;
else if(c[mid]<val) l=mid+1;
else r=mid-1;
}
return r;
}
int main()
{
int T;
ll ans;
scanf("%d",&T);
while(T--)
{
scanf("%lld%lld%lld",&n,&m,&k);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
for(int i=1;i<=m;i++) scanf("%lld",&b[i]);
for(int i=1;i<=k;i++) scanf("%lld",&c[i]);
sort(a+1,a+1+n);
sort(b+1,b+1+m);
sort(c+1,c+1+k);
ans=99999999999;
ll t,e;
ll maxn,sum;
for(int i=1;i<=n;i++)
{
sum=0;
maxn=9999999999;
t=solve1(a[i]);
if(abs(b[t]-a[i])<maxn&&t>=1&&t<=m) {maxn=abs(a[i]-b[t]);e=t;}
if(abs(b[t+1]-a[i])<maxn&&t+1>=1&&t+1<=m) {maxn=abs(a[i]-b[t+1]);e=t+1;}
if(abs(b[t-1]-a[i])<maxn&&t-1>=1&&t-1<=m) {maxn=abs(a[i]-b[t-1]);e=t-1;}
if(abs(b[t+2]-a[i])<maxn&&t+2>=1&&t+2<=m) {maxn=abs(a[i]-b[t+2]);e=t+2;}
if(abs(b[t-2]-a[i])<maxn&&t-2>=1&&t-2<=m) {maxn=abs(a[i]-b[t-2]);e=t-2;}
sum=sum+1+maxn+1;

maxn=9999999999;
t=solve2(b[e]);
if(abs(c[t]-b[e])<maxn&&t>=1&&t<=k) {maxn=abs(c[t]-b[e]);}
if(abs(c[t+1]-b[e])<maxn&&t+1>=1&&t+1<=k) {maxn=abs(c[t+1]-b[e]);}
if(abs(c[t-1]-b[e])<maxn&&t-1>=1&&t-1<=k) {maxn=abs(c[t-1]-b[e]);}
if(abs(c[t+2]-b[e])<maxn&&t+2>=1&&t+2<=k) {maxn=abs(c[t+2]-b[e]);}
if(abs(c[t-2]-b[e])<maxn&&t-2>=1&&t-2<=k) {maxn=abs(c[t-2]-b[e]);}
sum=sum+maxn+1;
if(sum<ans) ans=sum;
}
cout<<ans<<endl;
}
}

E—可以来拯救吗

题意：给一个长为n的序列，求所有长为k的子序列的和的平方的异或和(C(n,k)<=100000)

这个题就是dfs暴力，然后求结果就可以了，但是有两个坑。

1，当(n/2)<k时，转化成求C(n,n-k)，这样选的少，节省时间。

2，当n=k时特判，或者要注意。因为会有dfs不启动的情况。

代码：

#define ll long long
using namespace std;
ll a[100005];
ll b[100005];
ll c[100005];
ll cnt,n,k;
ll ans,u;
int flag;
ll t;
void solve1()
{
ll sum=0;
for(int i=1;i<=k;i++)
{
sum+=b[i];
//cout<<b[i]<<" ";
}
//cout<<endl;
sum=sum*sum;
c[++u]=sum;
}
void solve2()
{
ll sum=0;
for(int i=1;i<=k;i++)
{
sum+=b[i];
//cout<<b[i]<<" ";
}
//cout<<endl;
sum=t-sum;
sum=sum*sum;
c[++u]=sum;
}
void dfs(ll id,ll m)
{
if(m==k)
{
if(flag==1) solve1();
else if(flag==2) solve2();
return ;
}
if(m>k||id>n) return ;
for(int i=id+1;i<=n;i++)
{
b[m+1]=a[i];
dfs(i,m+1);
}
}
int main()
{
//cout<<(1^4^9);
int T;
scanf("%d",&T);
while(T--)
{
t=0;
scanf("%lld%lld",&n,&k);
for(int i=1;i<=n;i++) {scanf("%lld",&a[i]);t+=a[i];}
if(n==k) {cout<<t*t<<endl;continue;}
if(k==0) {cout<<0<<endl;continue;}
if(k<=(n/2)) {flag=1;}
else {flag=2;k=n-k;}
if(flag==1)
{
u=0;
for(int i=1;i<=n;i++)
{
cnt=0;
b[++cnt]=a[i];
dfs(i,cnt);
}
ans=0;
for(int i=1;i<=u;i++)
{
ans=ans^c[i];
}
}
else if(flag==2)
{
u=0;
for(int i=1;i<=n;i++)
{
cnt=0;
b[++cnt]=a[i];
dfs(i,cnt);
}
ans=0;
for(int i=1;i<=u;i++)
{
ans=ans^c[i];
}
}
cout<<ans<<endl;
}
}

F—汤圆防漏理论

题意：

这个汤圆和现在碗里与这个汤圆接触的所有汤圆之间的粘(nián)度的和，如果大于汤圆的硬度，这个汤圆就会被粘(zhān)漏。今天要煮n个汤圆，并且摆盘的方法已经设计好：汤圆按照编号，有m对汤圆互相接触，用xi, yi, zi表示编号为xi和yi的两个汤圆互相接触，粘(nián)度为zi。汤圆当然是越软越好吃，但是ghc的厨艺只允许把所有汤圆煮成同样的硬度。那么，汤圆的硬度最小可以是多少，可以满足吃的过程中，存在一种夹汤圆的顺序，使得没有汤圆会被粘(zhān)漏呢？

思路其实就是贪心，先建好这张图，将点存入容器，依次拿出年度最小和的点扔出，将边所连的点粘度更新，继续操作。这题就是对我们说太难写，一直调不通，，注意，最好不要用优先队列，用set。

代码：

来自：https://blog.csdn.net/qq_37685156/article/details/79833700

const int maxn=1e5+100;
typedef pair<ll,ll> pa;
set<pa> s; //set自动排序，按第一个关键字
vector<pa> g[maxn];
ll nd[maxn]; //汤圆的粘度
ll vis[maxn];
void init()
{
memset(nd,0,sizeof(nd));
for(int i=0;i<maxn;i++) g[i].clear();
s.clear();
memset(vis,0,sizeof(vis));
}
int main()
{
ll T;
cin>>T;
while(T--)
{
init();
ll n,m;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y,z;
cin>>x>>y>>z;
g[x].push_back(pa(y,z));
g[y].push_back(pa(x,z));
nd[x]+=z;
nd[y]+=z;
}
//将所有汤圆放入集合
for(int i=1;i<=n;i++) s.insert(make_pair(nd[i],i));
//一个一个取汤圆
ll ans=0;
while(!s.empty())
{
set<pa>::iterator it;
it=s.begin();
pa now=*it;
ans=max(ans,now.first);
s.erase(it);
//更新粘度
ll u=now.second;
vis[u]=1;
for(ll i=0;i<g[u].size();i++)
{
ll v=g[u][i].first;
if(vis[v]) continue;//只看父子边
it=s.find(pa(nd[v],v));
s.erase(it);
nd[v]-=g[u][i].second;
s.insert(pa(nd[v],v));
}
}
cout<<ans<<endl;
}
return 0;
}