Hello World

2026-02-27

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1	$ hexo new "My New Post"

More info: Writing

Run server

1	$ hexo server

More info: Server

Generate static files

1	$ hexo generate

More info: Generating

Deploy to remote sites

1	$ hexo deploy

More info: Deployment

暑假欢乐赛

2023-07-02

C 冒险

对于此题，我们的思想是贪心。

对于以上的图，我们发现，我们需要找到尽量重叠的一部分，对于完全不重叠的，我们就要单独计一个数。

这个原理有点像区间覆盖问题，给出几个区间，求能覆盖0~len的整个区间的最小可选区间数。

那么对于所有区间，我们设每一个区间的左端点下标为l，右端点下标为r。

证明得出，如果两个区间是重叠的，那么后面那个区间的左端点在前面那个区间的右端点的左边，而右端点在前面那个区间的右端点的右边。

我们按照先右端点由小到大，再左端点由大到小对区间排序，为什么是右端点，因为假设两个区间，按左端点排，会出现这个情况。

这样是会对后面区间的判断造成影响。

方法是遍历每一个区间，若满足以上条件，就不作为，否则它就是后面的不存在重合部分的区间，cnt+1，标志l和标志r分别改为该区间的l和r

code：

#include "bits/stdc++.h"
using namespace std;
struct node{
	int l,r;
}nd[100005];
bool cmp(node a,node b){
	if(a.r==b.r) return a.l<=b.l;
	return a.r<=b.r;
}
int main(){
	int len,n;
	cin>>len>>n;
	for(int i=1;i<=n;i++){
		cin>>nd[i].l>>nd[i].r;
	}
	sort(nd+1,nd+1+n,cmp);
	int u=nd[1].l,v=nd[1].r,cnt=1;

	for(int i=2;i<=n;i++){
		if(nd[i].l<=v&&nd[i].r>=v);
		if(nd[i].l>v) cnt++,u=nd[i].l,v=nd[i].r; 
	}
	cout<<cnt;
	return 0;
}

H 计算三元组

暴力方法是直接遍历i和j然后根据条件选择正确的k（i，j，k都是下标，所以数可能相同，但是下标不一样是分不同情况的）

我们直接在输入a数组元素的时候用一个二维数组记录每一个元素出现的位置。因为它是由小到大顺序输入的，所以不用排序了。

然后遍历i和j ， i != j 且a[ i ] != a[ j ] , 那么ak就等于s - a[ i ] - a[ j ]用二分法找到k下标大于j的第一个k（如果有多个相同的ak）然后之后的全都是各一种情况。

二分法用upper_bound( v[k].begin() , v[k].end() , j )会很方便。直接得到大于j的第一个下标。

code:

#include "bits/stdc++.h"
using namespace std;
int a[5005];
vector<int>v[100005];

int main(){
	int n,s;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];v[a[i]].push_back(i);
	}
	cin>>s;
	
	int cnt=0;
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			if(a[i]!=a[j]&&i<j){
				int k=s-a[i]-a[j];
				if(k>=0&&k!=a[i]&&k!=a[j]){
					int tt = upper_bound(v[k].begin(),v[k].end(),j)-v[k].begin();
					tt=v[k].size()-tt;  //计算满足条件的k数量
					cnt+=tt;
				}
			}
		}
	}
	cout<<cnt;
	return 0;
}

F 赛跑

首先我们的思路是对于每一个选手（数组中的每一个元素），查找他是所有元素中的第几名然后对于排名比他小的是可以都选的，对于排名比他大的可以选最多两个，因为规定是top3。

对于每一个人，我们假设前面有x个比它小的，后面有y个比它大的，那么可以选全部的x，而y部分最多只能选两个。有4种情况。

这个人排第一位，那么就选所有的x，除了只有它自己本身的那一个子集不选，那就是2^x-1
这个人排第二位，那么前面的x都可以选，然后从y中任意选一个。
这个人排第三位，那么前面x都可以选，然后从y中任意选两个。
这个人排第二位，但是就不选前面的x的部分了，相当于这个人就是最小的。则从后面y部分选一个。
这个人排第三位，但是就不选前面的x的部分了，相当于这个人就是最小的。则从后面y部分任意选两个。

那么要做到排序，首先要进行离散化过程。将数值映射成排名。

然后一些细节就是求2^x-1的时候要用快速幂，否则会被卡时间和空间。

离散化模板（实际上是根据不同需求做出修改）：

int C[MAXN], L[MAXN];
// 在main函数中...
memcpy(C, A, sizeof(A)); // 复制   A是投入的数组。
sort(C, C + n); // 排序
int l = unique(C, C + n) - C; // 去重
for (int i = 0; i < n; ++i)
    L[i] = lower_bound(C, C + l, A[i]) - C + 1; // 查找

链接：算法学习笔记(19): 离散化 - 知乎 (zhihu.com)

快速幂模板

const long long m=1e9+7;
long long quickpow(long long a,long long b){
	long long sum=1;
	while(b){
		if(b&1)//与运算，可判断奇偶，详细见注释
		sum=sum*a%m;//取模运算
		a=a*a%m;
		b>>=1;//位运算，右移，相当于除以2
	}
	return sum;
}

code :

#include "bits/stdc++.h"
using namespace std;
const int MAXN = 100005;
int A[MAXN],C[MAXN],L[MAXN];
int ans[MAXN];
const int md = 1e9+7;

//快速幂
long long quickpow(long long a,long long b){
	long long sum=1;
	while(b){
		if(b&1)//与运算，可判断奇偶，详细见注释
		sum=sum*a%md;//取模运算
		a=a*a%md;
		b>>=1;//位运算，右移，相当于除以2
	}
	return sum;
}


//typedef long long LL;
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>A[i];
	}
    //离散化步骤
	memcpy(C, A, sizeof(A)); 
	sort(C, C + n); 
	int l = unique(C, C + n) - C;   //长度 
	for (int i = 0; i < n; ++i)
    L[i] = lower_bound(C, C + l, A[i]) - C + 1; 
    
    //乘法原理求解（分情况）
    for(int i=0;i<n;i++){
	
		long long sum=0;
		int x=L[i]-1,y=n-L[i];

		sum = ((long long)((long long)y*(y-1)/2)+y)%md;
		sum = (sum+((long long)((long long)y*(y-1)/2)+y)%md*((long long)(quickpow(2,x)-1))%md)%md;		
		sum = (sum+(long long)(quickpow(2,x)-1))%md;

		cout<<sum<<" ";

	}
	return 0;
}

2023ccpc河南省赛vp记录

2023-05-23

快速幂求逆元

2023-05-16

题目：给定n组ai,pi，其中pi是质数,求ai模pi的乘法逆元，若逆元不存在则输出impossible。

（加竖线的符号是“>”）
背景：乘法逆元的定义：若整数b,m互质，并且对于任意的整数a，如果满足b|a则存在一个整数x，使得a/b = a*x(mod m),则称x是b的模m乘法逆元。记为b^(-1)(mod m)。b存在乘法逆元的充要条件是b与模数m互质，当模数m为质数时，b^(m-2)就是b的乘法逆元。
所以：x满足a/b和a*x(mod m)有相同的余数。只需求b^(m-2)。
解题代码如下：

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long LL;

//求(a^p-2)%p的快速幂
 LL quickmid(int a,int b,int p)
 {int res=1;
     while(b)
     {
         if(b&1)
         res=(LL)res*a%p;
         b>>=1;
         a=(LL)a*a%p;
     }
     return res;

 }


int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int a,p;
        scanf("%d%d",&a,&p);
        int res=quickmid(a,p-2,p);
        if(a%p)printf("%d\n",res);//当a=2,p=2,输出impossible
    else printf("impossible\n");
        
    }
}

第十九届西南科技大学ACM程序设计竟赛 (同步赛)

2023-05-10

E

01背包的变形，背包的容量是所有数字的总和，然后从数组中选择适当的元素放入背包，价值和代价都是元素的值。f[x]是x容量下最多可以装多少东西。题目要求装的东西的量各不相同，所以最后需要用set去重。
不去重的话结果如图

代码：

#include "bits/stdc++.h"
using namespace std;
int a[1005],f[10005];
set<int>s;
int main(){
    int n;
    cin>>n;
    int idx=0,sum=0,ans=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i];
    }
    for(int i=1;i<=n;i++)
        for(int j=sum;j>=a[i];j--){
            f[j]=max(f[j],f[j-a[i]]+a[i]);
        }
    for(int i=1;i<=sum;i++){
        if(f[i]) {
            s.insert(f[i]);           //去重
//         cout<<f[i]<<endl;
        }
    }
    cout<<s.size();
    return 0;
}

第一篇做题记录：cf872div2

2023-05-08

意思是固定最左上角的一个数，然后移动右下角，框出的矩形里面找最大最小值，相减，然后累加。
输入是输入这么多个数字，是可以自己排列在表里的。
思路：输入长宽的时候长在前宽在后，就是如果m<n要互换一下保证m>n.然后将填入的数组排一下序，一种做法是最左上角填入最大的数，然后这个位置的右方填入最小的数，下方填入第二小的数，可以证明这样相减得到的较大的值占的位置比较多。另一种做法是最左上角填入一个最小的数，这个位置的右方填入最大的数，下方填入第二大的数，两种做法分别求sum，最后比较这两个sum，求最大值就是ans。

代码：

#include "bits/stdc++.h"
using namespace std;
/**/
int a[105][105],b[100005];
int main()
{
    int n;
    cin>>n;
    while(n--){
        long long sum1=0,sum2=0;
        int p,q;
        cin>>p>>q;
        int tmp;
        if(p<q){
            tmp=p;
            p=q;
            q=tmp;
            
        }
        int x=p*q;
        for(int i=1;i<=x;i++) cin>>b[i];
        sort(b+1,b+1+x);
        sum1=(p-1)*q*(b[x]-b[1])+(q-1)*(b[x]-b[2]);
        sum2=(p-1)*q*(b[x]-b[1])+(q-1)*(b[x-1]-b[1]);
        long long ans=max(sum1,sum2);
        
        cout<<ans<<endl;
    }
    
    return 0;
}

题目大致意思就是有一排空的座位，现在有m个人，每个人对作座位的选择不同，-1代表坐在最左边的人的左边，如果现在没有人，那久坐在座位的最右边，-2和-1相反，代表坐在最右边的人的右边，如果现在没有一个人，那就坐在座位的最左边，其他>0的选择就坐在对应选择的位置上，以上如果位置有人坐了那他就离开，求一个方案能让尽量多的人坐上座位，实际上就是给一个入座的顺序使得他们能根据不同的需求坐上座位，使这个人数尽量多。
想法：
首先，如果有两个人都想坐Xi，那他们只能有一个人坐在那里。

然后，直接坐Xi位置的人不会影响前两种情况，例如：

>>>4>>7<<10<<13

你可以通过先放置一个情况三，在他两侧放置前两种情况的人，放置过程中如果当前位置有第三种人指定要坐，就i让他坐，然后继续排前两种情况。

所以Xi的人坐进去一定不会使答案变差。

然后以所有Xi作为中间点，进行上述排布求得1和2情况的最大排布数量，取个max，再加上Xi的数量，就是一般的情况。

ans = max( ans , min( i - v[i] , lf ) + min( m - ( v[m] - v[i] ) - i , ri ) );

v数组是Xi分布的前缀和，lf和ri是左右两种坐法的数量。

特殊的，我们可以或者只能从一侧开始排布，（即没有1或者2的情况），只需要对0和m+1作上述操作。

然后使用前缀和使得算法变成o（n）的时间复杂度。

代码：

#include "bits/stdc++.h"
using namespace std;
int a[100005];
int b[100005];
int main()
{
    int n;
    cin>>n;
    while(n--){
        int k,m;
        cin>>k>>m;
        int ans=0;
        int cnt1=0,cnt2=0;
        int idx=0;
        
        for(int i=1;i<=k;i++){
           int x;
            cin>>x;
            if(x==-1){cnt1++;continue;}
            if(x==-2){cnt2++;continue;}
          
            if(b[x]!=0) continue;
            b[x]=1;
            a[++idx]=x;//去重
        }
        
        
       for(int i=1;i<=m+1;i++) b[i]+=b[i-1];
        
        for(int i=1;i<=m;i++){
            if(b[i]-b[i-1]){
                ans=max(ans,min(i-b[i],cnt1)+min(m-(b[m]-b[i])-i,cnt2));
            }
        }
        ans=max(ans,min(m-(b[m]-b[0]),cnt2));
        ans=max(ans,min(m-b[m],cnt1));
        cout<<ans+idx<<endl;
        memset(b,0,sizeof(b));
    }
    
    return 0;
}

first blog test