1004传送门
题意：求\(\sum_{i=1}^n\) \(\mid\)a[i] * x+b[i]\(\mid\)=C(其中1<=ai<=1000，-1000<=b[i]<=1000)的所有解，如果解有无穷个则输出-1
题解：由于a[i]>=1，所以\(\mid\)a[i] * x+b[i]\(\mid\)的值在x=-b[i]/a[i]左边时-a[i] * x-b[i]，在x=-b[i]/a[i]右边时a[i] * x+b[i]，所以可以按照零点位置将n个绝对值式子排序，将数轴以这些点为界限分成若干区间，从左到右按顺序处理即可
#include<bits/stdc++.h>
using namespace std;
//#define debug(x) cout<<#x<<" is "<<x<<endl;
typedef long long ll;
const int maxn=1e5+5;
ll ans1[maxn],ans2[maxn];
struct pot{
ll a;
ll b;
}p[maxn];
bool cmp(struct pot aa,struct pot bb){
return bb.a*aa.b>aa.a*bb.b;
}
ll gcd(ll x,ll y){
if(y==0)return x;
return gcd(y,x%y);
}
int main(){
int t;
scanf("%d",&t);
while(t--){
ll n,c;
scanf("%lld%lld",&n,&c);
for(int i=1;i<=n;i++)scanf("%lld%lld",&p[i].a,&p[i].b);
sort(p+1,p+1+n,cmp);
ll s1=0;
ll s2=0;
int f=1;
int tot=0;
for(int i=1;i<=n;i++){s1-=p[i].a;s2-=p[i].b;}
if(s1==0&&s2==c){f=0;printf("-1\n");continue;}
if((s1>0&&(c-s2)*(p[1].a)<=(-s1*p[1].b))||(s1<0&&(c-s2)*(p[1].a)>=(-s1*p[1].b))){
if(c-s2==0){s1=1;}
ans1[++tot]=s1;
ans2[tot]=c-s2;
}
int j;
for(int i=1;i<=n;i=j){
j=i;
while(j<=n&&p[j].a*p[i].b==p[j].b*p[i].a){s1+=2*p[j].a;s2+=2*p[j].b;j++;}
if(s1==0&&s2==c){f=0;break;}
if(((j==n+1)||((s1>0&&(c-s2)*(p[j].a)<=(-s1*p[j].b))||(s1<0&&(c-s2)*(p[j].a)>=(-s1*p[j].b))))&&(((s1>0&&(c-s2)*(p[i].a)>=(-s1*p[i].b))||(s1<0&&(c-s2)*(p[i].a)<=(-s1*p[i].b))))){
if(tot){
if(ans2[tot]*s1==ans1[tot]*(c-s2))continue;
}
if(c-s2==0){s1=1;}
ans1[++tot]=s1;
ans2[tot]=c-s2;
}
}
if(f==0)printf("-1\n");
else{
printf("%d",tot);
for(int i=1;i<=tot;i++){
if(ans2[i]==0){printf(" 0/1");}
else{
int xx=gcd(ans1[i],ans2[i]);
int sgn=1;
if(ans2[i]*ans1[i]<0)sgn=-1;
printf(" %lld/%lld",sgn*abs(ans2[i]/xx),abs(ans1[i]/xx));
}
}
printf("\n");
}
}
return 0;
}
1005传送门
题意：求出一个1到n的n个数字的一个排列并且这个排列p[i+1]-p[i]的字典序第k小
题解：使用如下dfs直接搜索p[i+1]-p[i]的值可以比较容易地找到字典序第k小的方案，重点在于复杂度的分析(代码下方附上我的分析..如有错误望指正(>_<)..)
#include<bits/stdc++.h>
using namespace std;
//#define debug(x) cout<<#x<<" is "<<x<<endl;
typedef long long ll;
const int maxn=105;
bool vis[maxn*4];
int n,k,a[maxn];
int res;
bool dfs(int sum,int pos,int maxx,int minn){
if(pos==n-1){
res--;
if(!res){
int ss=n-maxx;
a[0]=0;
for(int i=1;i<=n;i++){
printf("%d",ss+a[i-1]);
ss+=a[i-1];
char cc=(i==n)?'\n':' ';
printf("%c",cc);
}
return 1;
}
return 0;
}
for(int i=1-n-sum+max(0,maxx);i<=n-sum-1+min(minn,0);i++){
if(vis[i+sum+200])continue;
vis[i+sum+200]=1;
a[pos+1]=i;
if(dfs(sum+i,pos+1,max(maxx,i+sum),min(minn,i+sum))){
vis[i+sum+200]=0;
return 1;
}
vis[i+sum+200]=0;
}
return 0;
}
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&k);
vis[200]=1;
res=k;
dfs(0,0,0,0);
}
return 0;
}
复杂度分析：由界定条件 for(int i=1-n-sum+max(0,maxx);i<=n-sum-1+min(minn,0);i++)保证这个dfs每次搜索的是一个p[i+1]-p[i]的排列，也就是不会出现搜索到无用结点的情况，每个结点最后都通向至少一个可行解，又由于只会搜索前k小的字典序，所以只有k个叶子结点，而每个被搜索到的结点都至少会被一个叶子结点经过，并且每个叶子结点到根的距离是n，所以至多会有kn个结点，而每个结点的复杂度为n，所以总的时间复杂度为O(kn*n)
1006传送门
题意：求以\(\sum_{i=1}^(n-1)\)F(i)，其中F(i)表示以s[i]开头的字符串与s[0]开头的字符串的相同前缀的长度
题解：exkmp裸题
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
char sa[1100000],sb[1100000];
int lena,lenb;
typedef long long ll;
ll p[1100000],ex[1100000];
//p数组是用来让B串自己匹配自己的
void exkmp()
{
p[1]=lenb;
int x=1;
while(sb[x]==sb[x+1]&&x+1<=lenb) x++;//因为我们p[1]是具有一定性，所以我们不能直接用，所以要先暴力求出p[2]
p[2]=x-1;
int k=2;
for(int i=3;i<=lenb;i++)
{
int pp=k+p[k]-1,L=p[i-k+1];//pp实际上是p
if(i+L<pp+1) p[i]=L;//i-k+L<pp-k+1化简后i+L<pp
else
{
int j=pp-i+1;
if(j<0) j=0;
while(sb[j+1]==sb[i+j]&&i+j<=lenb) j++;
p[i]=j;
k=i;
}
}
x=1;
while(sa[x]==sb[x]&&x<=lenb) x++;//ex[1]并不具有一定性，所以我们暴力求出ex[1]
ex[1]=x-1;
k=1;
for(int i=2;i<=lena;i++)
{
int pp=k+ex[k]-1,L=p[i-k+1];
if(i+L<pp+1) ex[i]=L;
else
{
int j=pp-i+1;
if(j<0) j=0;
while(sb[j+1]==sa[i+j]&&i+j<=lena&&j<=lenb) j++;
ex[i]=j;
k=i;
}
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--){
scanf("%s",sb+1);
lenb=strlen(sb+1);
lena=lenb-1;
for(int i=1;i<lenb;i++){
sa[i]=sb[i+1];
}
exkmp();
ll ans=lena;
for(int i=1;i<=lena;i++){ans+=ex[i];if(ex[i]+i>lena)ans--;}// printf("%d ",ex[i]);
printf("%lld\n",ans);
}
return 0;
}
1007传送门
题意：求题设要求的某种排列的方案数
题解：打表
#include<bits/stdc++.h>
using namespace std;
#define debug(x) cout<<#x<<" is "<<x<<endl;
typedef long long ll;
const int maxn=1e5+5;
const ll mod=998244353;
int a[maxn];
ll ans[maxn];
int main(){
ans[0]=ans[1]=ans[2]=1;
ans[3]=2;
for(int i=4;i<maxn;i++)ans[i]=(ans[i-1]+ans[i-3])%mod;
int t;
scanf("%d",&t);
while(t--){
ll n,x,y;
scanf("%lld%lld%lld",&n,&x,&y);
ll xx=max(x,y);
ll yy=min(x,y);
x=yy;
y=xx;
if(y!=n)y--;
if(x!=1)x++;
int xxx=y-x;
if(xxx<0)printf("0\n");
else printf("%lld\n",ans[xxx]);
}
return 0;
}
打表代码
#include<bits/stdc++.h>
using namespace std;
#define debug(x) cout<<#x<<" is "<<x<<endl;
typedef long long ll;
const int maxn=1e5+5;
const ll mod=998244353;
int a[maxn];
int main(){
while(1){
int n,x,y;
scanf("%d%d%d",&n,&x,&y);
int tot=0;
a[0]=x;
a[n-1]=y;
int ac=0;
for(int i=1;i<=n;i++){
if(i==x||i==y)continue;
a[++tot]=i;
}
do{
int f=1;
for(int i=1;i<=n-1;i++){
if(abs(a[i]-a[i-1])>2){f=0;break;}
}
if(f){
ac++;
}
}while(next_permutation(a+1,a+1+tot));
printf("%d\n",ac);
}
return 0;
}