文章目录
- A. Maximal Binary Matrix
- B. Distances to Zero
- C. Maximal GCD
- D. Magazine Ad
- E. Roma and Poker
A. Maximal Binary Matrix
思路：一道很有意思的构造，我们可以发现，按照下述，从外到内进行一层一层的构造一定是最优的。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
int mod = 1e9+7;
const int maxv = 4e6 + 5;
// #define endl "\n"
int a[105][105];
int n,k;
void solve()
{
cin>>n>>k;
if(k>n*n){
cout<<-1<<endl;
return ;
}
int f=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(k==0) {
f=1;
break;
}
if(a[i][j]) continue;
if(i==j) a[i][j]=1,k--;
else{
if(k>=2) a[i][j]=a[j][i]=1,k-=2;
}
}
if(f) break;
}
for(int l=1;l<=n;l++){
for(int r=1;r<=n;r++) cout<<a[l][r]<<" ";
cout<<endl;
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
t=1;
// cin>>t;
while(t--){
solve();
}
system("pause");
return 0;
}
B. Distances to Zero
给你一个由整数 a0, a1, …, an - 1 组成的数组。求每个元素到最近的零的距离(到等于零的元素的距离)。给定数组中至少有一个零元素。
思路：我们考虑除了首尾元素和0的距离，若其左方存在0，并且右方存在0，那么我们可以从前往后扫一遍，然后从后往前扫一遍，就可以求出每个元素到0的最短距离。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
int mod = 1e9+7;
const int maxv = 4e6 + 5;
// #define endl "\n"
int ans[N];
void solve()
{
int n;
cin>>n;
vector<int> a(n+5);
memset(ans,0x3f,sizeof ans);
for(int i=1;i<=n;i++) cin>>a[i];
int last=-1;
for(int i=1;i<=n;i++){
if(a[i]==0){
ans[i]=0,last=i;
}
if(last==-1) continue;
else{
ans[i]=(i-last);
}
}
last=-1;
for(int i=n;i>=1;i--){
if(a[i]==0){
ans[i]=0,last=i;
}
if(last==-1) continue;
else{
ans[i]=min(ans[i],last-i);
}
}
for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
cout<<endl;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
t=1;
// cin>>t;
while(t--){
solve();
}
system("pause");
return 0;
}
C. Maximal GCD
给你一个正整数 n 。你应该创建这样一个由 k 个正数 a1, a2, …, ak 组成的 严格递增序列，使它们的和等于 n ，且最大公约数为最大值。
数列的最大公约数是数列中每个元素都能被它们整除的数的最大值。
如果不存在可能的序列，则输出 -1.
思路：感觉不能随便构造出来，所有考虑对于数列的最大公约数进行枚举，然后取最大的合法序列即可，但暴力枚举 1 − n 1-n 1−n肯定会超时，考虑优化，我们会发现，整个数列的最大公约数，一定是n的因子。
证明：设最大公因数为 k ,那么我们构造最小的严格递增序列为 k ∗ 1 , k ∗ 2 , k ∗ 3...... k ∗ ( i − 1 ) , k ∗ i k*1,k*2,k*3......k*(i-1),k*i k∗1,k∗2,k∗3......k∗(i−1),k∗i,其和等于 k ,那么把 k 提出来，就得到 n / k 为一个常数，因此得证。
又因为 n 的范围为1e10，枚举因数的时间复杂度为 n \sqrt{n} n,所以只需要对 n 进行质因数分解，然后一一枚举取最大值即可。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
int mod = 1e9+7;
const int maxv = 4e6 + 5;
// #define endl "\n"
void solve()
{
ll n,k;
cin>>n>>k;
__int128_t sum=(1+k)*(__int128_t)k/2;//注意题目为1e10的数据范围，所以ll存不下，要么使用int128，要么对式子进行变形
if(sum>n){
cout<<-1<<endl;
return ;
}
vector<ll> a;
for(int i=1;i<=n/i;i++){
if(n%i==0){
a.push_back(i);
if(n/i!=i) a.push_back(n/i);
}
}
ll ans=-1;
for(auto x: a){
if(n%x==0){
ll cnt=n/x;
if(cnt>=sum){
ans=max(ans,x);
}
}
}
if(ans==-1){
cout<<ans<<endl;
return;
}
else{
ll cnt=0;
for(int i=1;i<=k-1;i++){
cout<<ans*i<<" ";
cnt+=i;
}
ll tot=n/ans;
cout<<(tot-cnt)*ans<<endl;
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
t=1;
// cin>>t;
while(t--){
solve();
}
system("pause");
return 0;
}
D. Magazine Ad
思路：二分答案
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
int mod = 1e9+7;
const int maxv = 4e6 + 5;
// #define endl "\n"
int k;
vector<int> a;
vector<string> ss;
bool check(int x)
{
int h=1;
int sum=0;
for(auto len: a){
if(len>x) return false;
if(sum+len>x){
sum=len;
h++;
}
else sum+=len;
}
return h<=k;
}
void solve()
{
cin>>k;
string s;
while(cin>>s){
ss.push_back(s);
}
for(int i=0;i<ss.size();i++){
string s=ss[i];
int sum=0;
for(int i=0;i<s.size();i++){
if(s[i]=='-'){
a.push_back(sum+1);
sum=0;
}
else sum++;
}
if(sum){
if(i==ss.size()-1) a.push_back(sum);
else a.push_back(sum+1);
}
}
int l=0,r=1e9+5;
int ans=0;
while(l<=r){
int mid=(l+r)/2;
if(check(mid)){
ans=mid;
r=mid-1;
}
else l=mid+1;
}
cout<<ans<<endl;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
t=1;
//cin>>t;
while(t--){
solve();
}
system("pause");
return 0;
}
E. Roma and Poker
每天晚上，罗姆都会在他最喜欢的网站上玩在线扑克。这个网站上的扑克规则有点奇怪：一手牌总是有两个玩家，没有赌注，赢家从输家那里拿走 1 个虚拟布尔。
昨天晚上，罗姆开始玩扑克。他决定花费不超过 k 个虚拟布尔 - 如果输的比赢的多 k 个，他将立即停止游戏。此外，如果 Roma 赢的钱够他玩一晚上，即赢的钱比输的钱多 k ，他就会离开游戏。
第二天早上，罗姆发现了一张纸，上面有一个代表他结果的序列。罗马记不清楚结果了，而且序列中有些字符的写法让人无法辨认，所以罗马记不起自己是赢了 k 布尔还是输了。
Roma 写的序列是一个字符串 s ，由字符 W (Roma 赢了相应的一手牌)、L (Roma 输了)、D (平局)和 ? (未知结果)组成。罗姆希望通过将所有 ? 字符更改为 W, L 或 D 来恢复任何 valid 序列。如果满足所有这些条件，该序列就称为 valid 序列：
最终胜负数的绝对差等于 k ；
没有一手牌的绝对差等于 k 。
帮助 Roma 恢复任何这样的序列。
思路：限制条件比较多，考虑差分约束。
如果当前为W,则
d
i
−
d
i
−
1
=
1
d_i-d_{i-1}=1
di−di−1=1
如果当前为D,则
d
i
−
d
i
−
1
=
0
d_i-d_{i-1}=0
di−di−1=0
如果当前为L,则
d
i
−
d
i
−
1
=
−
1
d_i-d_{i-1}=-1
di−di−1=−1
考虑两者之间差的绝对值不大于1，则
∣
d
i
−
d
i
−
1
∣
≤
1
|d_i-d_{i-1}|\le1
∣di−di−1∣≤1
考虑到第 i 位为止，其前缀和小于等于k，则
∣
d
i
−
d
0
∣
≤
k
−
1
|d_i-d_{0}|\le k-1
∣di−d0∣≤k−1
考虑最终差值位 k ，则
∣
d
n
−
d
0
∣
=
k
|d_n-d_0|=k
∣dn−d0∣=k
根据上述进行不等式转换即可。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
int mod = 1e9+7;
const int maxv = 4e6 + 5;
// #define endl "\n"
vector<pll> e[N];
void add(int u,int v,int w)
{
e[u].push_back({v,w});
}
int cnt[N];
int st[N];
ll d[N];
int n,k;
bool spfa()
{
for(int i=0;i<=n;i++) d[i]=2e9,st[i]=cnt[i]=0;
d[0]=0,st[0]=1;
queue<int> q;
q.push(0);
while(!q.empty()){
int t=q.front();
q.pop();
st[t]=0;
for(auto [u,w]: e[t]){
if(d[u]>d[t]+w){
d[u]=d[t]+w;
if(!st[u]){
st[u]=1;
q.push(u);
cnt[u]++;
if(cnt[u]>n) return false;
}
}
}
}
return true;
}
void solve()
{
cin>>n>>k;
string s;
cin>>s;
//n=s.size();
s=" "+s;
for(int i=1;i<=n;i++){
if(s[i]=='W'){
add(i-1,i,1);
add(i,i-1,-1);
}
else if(s[i]=='D'){
add(i-1,i,0),add(i,i-1,0);
}
else if(s[i]=='L') add(i-1,i,-1),add(i,i-1,1);
else add(i-1,i,1),add(i,i-1,1);
if(i<n) add(i,0,k-1),add(0,i,k-1);
}
add(0,n,k),add(n,0,-k);
if(spfa()){
for(int i=1;i<=n;i++){
// cout<<d[i]<<" ";
if(d[i]-d[i-1]==1) cout<<"W";
else if(d[i]-d[i-1]==0) cout<<"D";
else cout<<"L";
}
cout<<endl;
return;
}
e[n].pop_back();
e[0].pop_back();
add(0,n,-k),add(n,0,k);
if(spfa()){
for(int i=1;i<=n;i++){
// cout<<d[i]<<" ";
if(d[i]-d[i-1]==1) cout<<"W";
else if(d[i]-d[i-1]==0) cout<<"D";
else cout<<"L";
}
cout<<endl;
return;
}
cout<<"NO"<<endl;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
t=1;
//cin>>t;
while(t--){
solve();
}
system("pause");
return 0;
}
