每日n题0309

整数小拼接

题目链接：
P8708 [蓝桥杯 2020 省 A1] 整数小拼接 - 洛谷
思路：
如果通过暴力循环去一个一个找的话能过 30 分。

const int N=1e5+5;
int a[N];
int n,k;
bool check(int aa,int bb){
    string s;
    s=to_string(aa)+to_string(bb);
    int p=stoll(s);//string 转 longlong
    return p<=k;
}
void solve()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i==j)continue;
            if(check(a[i],a[j])){
                cnt++;
            }
        }
    }
    cout<<cnt;
}

为了更好的做题，我们先给数组排个序。这样就好找规律了。
要使拼出来的数字小于等于 k，所以我们可以分析一下满足条件的 j 的取值。
如果我们将 a[j] 拼到 a[i] 后面，可以知道随着 i 的增大满足条件的 j 的个数会变少。
然后有进行了一次优化能过一半分数。

bool check(int aa,int bb){
    string s;
    s=to_string(aa)+to_string(bb);
    int p=stoll(s);
    return p<=k;
}
void solve()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i==j)continue;
            if(check(a[i],a[j]))cnt++;
            else break;
        }
    }
    cout<<cnt;
}

这样还是超时的话，只能再考虑双指针优化了。

正解代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define PII pair<int,int>
const int N=1e5+5;
int a[N];
int n,k;
bool check(int aa,int bb){
    string s;
    s=to_string(aa)+to_string(bb);
    int p=stoll(s);
    return p<=k;
}
void solve()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    int cnt=0;
    int r=n;
    for(int i=1;i<=n;i++)
    {
        while(r>0&&!check(a[i],a[r]))r--;
        cnt+=r;
        if(r>=i)cnt--;
    }
    cout<<cnt;
}
signed main(){
	IOS
	//int t;
	//cin>>t;
	int t=1;
	while(t--)
	{
		solve();
	}
}

宇宙总统

题目链接：

P1781 宇宙总统 - 洛谷

思路：

总感觉做过，就是转成字符串比较。

代码：

bool check(string a,string b){
    if(a.size()>b.size())return true;
    else if(a.size()<b.size())return false;
    else{
        for(int i=0;i<a.size();i++)
        {
            if(a[i]>b[i])return true;
            else if(a[i]<b[i])return false;
        }
        return true;
    }
}
void solve()
{
    int n;
    cin>>n;
    string m="0";
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        string x;
        cin>>x;
        if(check(x,m))
        {
            cnt=i;
            m=x;
        }
    }
    cout<<cnt<<endl<<m;
}

全排列的价值

题目链接：

P12369 [蓝桥杯 2022 省 Python B] 全排列的价值 - 洛谷

思路：

题目所描述的价值其实就是顺序对的数量。
对于 n 个数，所产生的全排列数是 ，在所有排列中顺序对出现的概率是 。所以一个特定位置 在 个排列中是顺序对。
在一个排列中一共有多少种位置选择？ 种。
所以所有排列中的顺序对数量为：。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define PII pair<int,int>
const int MOD=998244353;
const int N=1e6+5;
int infact[N],fact[N];
int qmi(int a,int b,int p){
    int res=1;
    while(b){
        if(b&1)res=res*a%p;
        b>>=1;
        a=a*a%p;
    }
    return res%p;
}
void pre(){
    fact[0]=1,infact[0]=1;
    for(int i=1;i<=N;i++){
        fact[i]=fact[i-1]*i%MOD;
    }
}
void solve()
{
    int n;
    cin>>n;
    int cnt=0;
    cout<<fact[n]*n%MOD*(n-1)%MOD*qmi(4,MOD-2,MOD)%MOD;
}
signed main(){
	IOS
	//int t;
	//cin>>t;
	int t=1;
    pre();
	while(t--)
	{
		solve();
	}
}

狡兔 k 窟

题目链接：

P12126 [蓝桥杯 2024 省 B 第二场] 狡兔 k 窟 - 洛谷

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define PII pair<int,int>
const int N=2e5+5;
int c[N];
const int M=4e5+5;
int e[N],ne[M],h[M],idx,w[M];
int dist[N];
bool st[N];
void add(int a,int b,int c)
{
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}
void bfs(int u,int v){
    memset(dist,0x3f,sizeof dist);
    memset(st,0,sizeof st);
    dist[u]=0;
    queue<int>q;
    q.push(u);
    while(q.size()){
        auto t=q.front();
        q.pop();
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            if(dist[j]>dist[t]+w[i]){
                dist[j]=dist[t]+w[i];
                q.push(j);
            }
        }
    }
    cout<<dist[v]<<endl;
}
void solve()
{
    int n,m;
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++)
    {
        cin>>c[i];
    }
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        u=c[u],v=c[v];
        add(u,v,1);
        add(v,u,1);
    }
    while(m--){
        int s,t;
        cin>>s>>t;
        bfs(c[s],c[t]);
    }
}
signed main(){
	IOS
	//int t;
	//cin>>t;
	int t=1;
	while(t--)
	{
		solve();
	}
}

管道

题目链接：
P12380 [蓝桥杯 2023 省 Python B] 管道 - 洛谷
思路：
二分时间。
代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define PII pair<int,int>
const int N=1e5+5;
int L[N],S[N];
int n,len;
bool check(int mid){
    int p=0;
    for(int i=1;i<=n;i++)
    {
        if(mid>=S[i]){
            if(p>=len)return true;
            int l=L[i]-(mid-S[i]);
            int r=L[i]+(mid-S[i]);
            if(l-1<=p)p=max(p,r);
        }
    }
    if(p>=len)return true;
    return false;
}
void solve()
{
    cin>>n>>len;
    for(int i=1;i<=n;i++)
    {
        cin>>L[i]>>S[i];
    }
    int l=1,r=2e9;
    while(l<r){
        int mid=l+r>>1;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    cout<<l;
}
signed main(){
	IOS
	//int t;
	//cin>>t;
	int t=1;
	while(t--)
	{
		solve();
	}
}