给定 ,求出
并且
要最小,
,满足
可以写成
,根据
可以推出
即,因为
,所以两边可以减去最大的整数
.
变成,再倒过来变成
，重复以上步骤直到两端点之间有整数时
取最小的整数,
，所以可以用辗转相除法得到.
#include<bits/stdc++.h>
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define itn int
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
#define STR clock_t startTime = clock();
#define END clock_t endTime = clock();cout << double(endTime - startTime) / CLOCKS_PER_SEC *1000<< "ms" << endl;
using namespace std;
const int N=1e6;
const long long mod=1e9+7;
const long long mod2=998244353;
const int oo=0x7fffffff;
const int sup=0x80000000;
typedef long long ll;
typedef unsigned long long ull;
template <typename it>void db(it *begin,it *end){while(begin!=end)cout<<(*begin++)<<" ";puts("");}
template <typename it>
string to_str(it n){string s="";while(n)s+=n%10+'0',n/=10;reverse(s.begin(),s.end());return s;}
template <typename it>int o(it a){cout<<a<<endl;return 0;}
ll mul(ll a,ll b,ll c){ll ans=0;for(;b;b>>=1,a=(a+a)%c)if(b&1)ans=(ans+a)%c;return ans;}
ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=mul(a,a,c))if(b&1)ans=mul(ans,a,c);return ans;}
void dfs(ll p1,ll x1,ll p2,ll x2,ll &b,ll &y){
ll z=p1/x1+1;
if(z<=p2/x2){
b=z,y=1;
return ;
}
p1-=(z-1)*x1;p2-=(z-1)*x2;
dfs(x2,p2,x1,p1,y,b);
b+=(z-1)*y;//原式减去了(z-1)*y,要加回.
}
int main(){
//STR;
//IN OUT
int t;cin>>t;
while(t--){
ll p,x;
sc("%lld%lld",&p,&x);
ll a,b,y;
dfs(p,x,p,x-1,b,y);
a=b*x-p*y;
printf("%lld/%lld\n",a,b);
}
//END
}HDU-6625 three arrays
给定个数组
,要求一个
数组,
数组中的数可以由
数组各选一个数异或得到,求
数组,最小字典序输出.
数组分别建一棵
,每次贪心取
，若都没有相同的则随便往哪条支路走.
#include<bits/stdc++.h>
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define itn int
using namespace std;
const int N=2e6;
const long long mod=1e9+7;
const long long mod2=998244353;
const int oo=0x7fffffff;
const int sup=0x80000000;
typedef long long ll;
typedef unsigned long long ull;
template <typename it>void db(it *begin,it *end){while(begin!=end)cout<<(*begin++)<<" ";puts("");}
template <typename it>
string to_str(it n){string s="";while(n)s+=n%10+'0',n/=10;reverse(s.begin(),s.end());return s;}
template <typename it>int o(it a){cout<<a<<endl;return 0;}
ll mul(ll a,ll b,ll c){ll ans=0;for(;b;b>>=1,a=(a+a)%c)if(b&1)ans=(ans+a)%c;return ans;}
ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=mul(a,a,c))if(b&1)ans=mul(ans,a,c);return ans;}
int Trie[2][N][2];
int val[2][N];
int a[N],b[N],tot[2];
void insert(int op,int x){
int next=0;
for(int i=30;i>=0;i--){
int key=x>>i&1;
if(Trie[op][next][key]==0){
Trie[op][next][key]=++tot[op];
Trie[op][Trie[op][next][key]][0]=0;
Trie[op][Trie[op][next][key]][1]=0;
}
next=Trie[op][next][key];
val[op][next]++;
}
}
int QAQ(){
int ans=0;
int nx1=0,nx2=0;
for(int i=30;i>=0;i--){
if(val[0][Trie[0][nx1][0]]&&val[1][Trie[1][nx2][0]]){
val[0][Trie[0][nx1][0]]--;
val[1][Trie[1][nx2][0]]--;
nx1=Trie[0][nx1][0];
nx2=Trie[1][nx2][0];
}else if(val[0][Trie[0][nx1][1]]&&val[1][Trie[1][nx2][1]]){
val[0][Trie[0][nx1][1]]--;
val[1][Trie[1][nx2][1]]--;
nx1=Trie[0][nx1][1];
nx2=Trie[1][nx2][1];
}else if(val[0][Trie[0][nx1][0]]&&val[1][Trie[1][nx2][1]]){
ans+=1<<i;
val[0][Trie[0][nx1][0]]--;
val[1][Trie[1][nx2][1]]--;
nx1=Trie[0][nx1][0];
nx2=Trie[1][nx2][1];
}else if(val[0][Trie[0][nx1][1]]&&val[1][Trie[1][nx2][0]]){
ans+=1<<i;
val[0][Trie[0][nx1][1]]--;
val[1][Trie[1][nx2][0]]--;
nx1=Trie[0][nx1][1];
nx2=Trie[1][nx2][0];
}
}
return ans;
}
int main(){
//clock_t startTime = clock();
//freopen("in.txt","r",stdin);
me(val,0);me(Trie,0);
int t;cin>>t;
while(t--){
Trie[0][0][0]=Trie[0][0][1]=Trie[1][0][0]=Trie[1][0][1]=0;
val[0][0]=0;val[1][0]=0;
tot[0]=tot[1]=0;
int n;sc("%d",&n);
for(int i=1;i<=n;i++){sc("%d",a+i);insert(0,a[i]);}
for(int i=1;i<=n;i++){sc("%d",b+i);insert(1,b[i]);}
vector<int>ans;
for(int i=1;i<=n;i++)ans.push_back(QAQ());
sort(ans.begin(),ans.end());
for(int i=0;i<n;i++)printf("%d%c",ans[i]," \n"[i==n-1]);
}
//clock_t endTime = clock();
//cout << double(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;
}
给定求解方程
的根.
首先很重要的条件，每条直线的斜率大于
,如图:
根据零点分布可以划分个区间,
在其中一个区间时,左边的直线可以直接去绝对值,右边的直线去绝对值要加负号,所以可以合并成一条直线判断解是否在那个区间即可,求个
前缀和可以降低复杂度，关键点:每条直线斜率都大于
.
#include<bits/stdc++.h>
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define itn int
#define STR clock_t startTime = clock();
#define END clock_t endTime = clock();cout << double(endTime - startTime) / CLOCKS_PER_SEC *1000<< "ms" << endl;
using namespace std;
const int N=1e6;
const long long mod=1e9+7;
const long long mod2=998244353;
const int oo=0x7fffffff;
const int sup=0x80000000;
typedef long long ll;
typedef unsigned long long ull;
template <typename it>void db(it *begin,it *end){while(begin!=end)cout<<(*begin++)<<" ";puts("");}
template <typename it>
string to_str(it n){string s="";while(n)s+=n%10+'0',n/=10;reverse(s.begin(),s.end());return s;}
template <typename it>int o(it a){cout<<a<<endl;return 0;}
ll mul(ll a,ll b,ll c){ll ans=0;for(;b;b>>=1,a=(a+a)%c)if(b&1)ans=(ans+a)%c;return ans;}
ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=mul(a,a,c))if(b&1)ans=mul(ans,a,c);return ans;}
itn n,c;
ll sa[N]={0},sb[N]={0};
struct node{
int a,b;
bool friend operator <(node x,node y){
return x.b*y.a>x.a*y.b;
}
}line[N];
int main(){
//STR
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int t;cin>>t;
while(t--){
sc("%d%d",&n,&c);
for(int i=1;i<=n;i++){
sc("%d%d",&line[i].a,&line[i].b);
}
sort(line+1,line+1+n);
for(int i=1;i<=n;i++)sa[i]=sa[i-1]+line[i].a,sb[i]=sb[i-1]+line[i].b;
vector<pair<ll,ll>>Q;
if(sa[n]==0&&(-sb[n]==c||sb[n]==c)){
o(-1);continue;
}
if(sa[n]!=0&&1LL*line[1].a*(c+sb[n])>=1LL*line[1].b*sa[n]){
ll x=sb[n]+c,y=-sa[n];
ll g=__gcd(x,y);
x/=g,y/=g;
if(y<0)x=-x,y=-y;
Q.push_back({x,y});
}
bool BOOl=false;
for(int i=1;i<n;i++){
ll ai=2LL*sa[i]-sa[n],bi=2LL*sb[i]-sb[n];
if(ai==0&&c==bi){BOOl=true;o(-1);break;}
if(ai!=0){
if(-line[i].b*1.0/line[i].a<(c-bi)*1.0/ai&&(c-bi)*1.0/ai<=-line[i+1].b*1.0/line[i+1].a){
ll x=c-bi,y=ai;
ll g=__gcd(x,y);
x/=g,y/=g;
if(y<0)x=-x,y=-y;
Q.push_back({x,y});
}
}
}
if(BOOl)continue;
if(sa[n]!=0&&(0LL+c-sb[n])*line[n].a>sa[n]*(-line[n].b)){
ll x=c-sb[n],y=sa[n];
ll g=__gcd(x,y);
x/=g,y/=g;
if(y<0)x=-x,y=-y;
Q.push_back({x,y});
}
int sz=unique(Q.begin(),Q.end())-Q.begin();
printf("%d",sz);
for(int i=0;i<sz;i++)printf(" %lld/%lld",Q[i].first,Q[i].second);
puts("");
}//END
}
找出一个排列的字典序第
小排列输出.字典序判断标准是
.
因为最大时
，所以
时直接按合法序列输出,
时暴力即可.
#include<bits/stdc++.h>
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define itn int
#define cas int t;cin>>t;while(t--)
using namespace std;
const int N=1e6;
const long long mod=1e9+7;
const int oo=0x7fffffff;
const int sup=0x80000000;
typedef long long ll;
typedef unsigned long long ull;
template <typename it>void db(it *begin,it *end){while(begin!=end)cout<<(*begin++)<<" ";puts("");}
template <typename it>
string to_str(it n){string s="";while(n)s+=n%10+'0',n/=10;reverse(s.begin(),s.end());return s;}
template <typename it>int o(it a){cout<<a<<endl;return 0;}
ll mul(ll a,ll b,ll c){ll ans=0;for(;b;b>>=1,a=(a+a)%c)if(b&1)ans=(ans+a)%c;return ans;}
ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=mul(a,a,c))if(b&1)ans=mul(ans,a,c);return ans;}
bool cmp(vector<pair<int,int> >a,vector<pair<int,int> >b){
int sz=a.size();
for(int i=0;i<sz;i++){
if(a[i].second==b[i].second)continue;
if(a[i].second<b[i].second)return true;
else return false;
}
}
int main(){
//freopen("in.txt","r",stdin);
cas{
int n,k;
sc("%d%d",&n,&k);
if(n>8){
vector<int>a;
for(int i=1;i<n;i++)a.push_back(i);
do{
k--;
if(k==0){
printf("%d",n);
for(int x:a)printf(" %d",x);
puts("");
break;
}
}while(next_permutation(a.begin(),a.end()));
}else{
vector<vector<pair<int,int> > >a;
vector<int>all;
for(int i=1;i<=n;i++)all.push_back(i);
do{
vector<pair<int,int> >x;
for(int i=0;i<n;i++){
if(i){
x.push_back({all[i],all[i]-all[i-1]});
}else x.push_back({all[i],0});
}
a.push_back(x);
}while(next_permutation(all.begin(),all.end()));
sort(a.begin(),a.end(),cmp);
for(int i=0;i<n;i++)printf("%d%c",a[k-1][i].first," \n"[i==n-1]);
}
}
}
输出比较次数.
扩展数组的性质
#include<bits/stdc++.h>
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define itn int
using namespace std;
const int N=1e6+5;
const long long mod=1e9+7;
const long long mod2=998244353;
const int oo=0x7fffffff;
const int sup=0x80000000;
typedef long long ll;
typedef unsigned long long ull;
template <typename it>void db(it *begin,it *end){while(begin!=end)cout<<(*begin++)<<" ";puts("");}
template <typename it>
string to_str(it n){string s="";while(n)s+=n%10+'0',n/=10;reverse(s.begin(),s.end());return s;}
template <typename it>int o(it a){cout<<a<<endl;return 0;}
ll mul(ll a,ll b,ll c){ll ans=0;for(;b;b>>=1,a=(a+a)%c)if(b&1)ans=(ans+a)%c;return ans;}
ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=mul(a,a,c))if(b&1)ans=mul(ans,a,c);return ans;}
char s[N];
int ex[N];
int main(){
int t;cin>>t;
while(t--){
sc("%s",s);
int mix=0,L=0;
int n=strlen(s);
for(int i=1;i<n;i++){
if(i>=mix)ex[i]=0;
else ex[i]=min(mix-i,ex[i-L]);
while(s[ex[i]]==s[ex[i]+i])ex[i]++;
if(i+ex[i]>mix)mix=i+ex[i],L=i;
}
ll ans=0;
for(int i=1;i<n;i++){
ans++;
if(ex[i]){
ans+=ex[i];
if(i+ex[i]==n)ans--;
}
if(i+ex[i]>n)break;
}
printf("%lld\n",ans);
}
}
排列满足以下关系:
这样的排列有多少个
没有限制的时候可以得到递推关系:
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int a[N];
void init()
{
a[1]=1;a[2]=1;a[3]=1;
for(int i=4;i<N;i++)
a[i]=(a[i-1]+a[i-3])%998244353;
}
int main()
{
init();
int t;
scanf("%d",&t);
while(t--)
{
int n,x,y;
scanf("%d%d%d",&n,&x,&y);
if(x==1)
{
if(y==n) printf("%d\n",a[y]);
else printf("%d\n",a[y-1]);
}else if(y==n)
{
printf("%d\n",a[y-x]);
}else
{
printf("%d\n",a[y-x-1]);
}
}
}
京公网安备 11010502036488号