ECUST_Algorithm_2019_1
简要题意及解析
求\(a+b\)。
数据范围很大，用int或者long long不行。Java和python可以使用大数直接写。
高精度加法：做法就是将数据读入字符串中，数组的每一个单元存一位数，像列竖式一样用循环模拟计算就好辣。
需要注意只有两组数据输出之间需要空行，最后不要多输出一个换行。
时间复杂度\(O(Tn)\)
\(T\)为数据组数，\(n\)为数字位数。
求两个数字之间的完数数量。注意两个端点不一定按照升序给出。
首先解决如何判断一个数是不是完数，只需要找到它的所有因数求和判断一下即可。
找\(n\)的因数只需要从\(1\)枚举到\(\sqrt{n}\)，因为找到一个小于\(\sqrt{n}\)的因数之后即可求出另一个大于\(\sqrt{n}\)的因数。注意判断完全平方数。
建议预处理出所有完全平方数，使用一个数组\(sum[i]\)存储\([1,i]\)这个区间一共多少个完全平方数。每组询问即可\(O(1)\)回答。
时间复杂度\(O(\sqrt{m}+T)\)
\(m\)是数字的最大值，\(T\)是数据组数。
求一个矩阵\(k\)次方的迹。
\(k\)的值很大，需要使用快速幂。快速幂是一种使用分治法将幂次折半递归求解的算法，时间复杂度\(O(k)\)。
本题还需要矩阵乘法。
关于取模：先全部算出来再取模会出问题，因为中间运算结果太大存不下。其实取模的本质是减法，一边算一边取模即可，具体可百度同余原理。
时间复杂度\(O(T*n^3*logk)\)
\(T\)是数据组数，\(n\)是矩阵大小，\(k\)是幂次。
求一个区间中所有偶数的平方和以及所有奇数的立方和。
没有给出区间的范围，但是平方和立方增长很快，题目也保证答案不超过2^32，因此询问区间不会太长。对于每组询问，直接循环判断求和即可。
时间复杂度\(O(TL)\)
\(T\)为数据组数，\(L\)为询问长度。
汉诺塔问题，多加一根柱子。
多手推一些数据会发现这样决策是最优的：
当前目标为把\(n\)个盘从\(1\)号柱移动到\(4\)号柱。2，3，4号柱均可作为盘的“中转点”。设解决这个问题消耗的次数为\(f(i)\)。
1.把最上面\(i\)个盘移动到\(2\)号柱。
2,3,4号柱均可作为盘的“中转点”。这是和原问题性质一样的子问题。
2.把剩下的\(n-i\)个盘移动到\(4\)号柱。
3,4号柱可以作为盘的“中转点”，因为这时2号柱上的\(i\)个盘子小，不能把这\(n-i\)个中的任何一个放上去。容易发现，这个问题是经典(正常)的汉诺塔问题，需要的移动次数为\(2^{n-i}-1\)。
3.把2号柱上\(i\)个盘移动到\(4\)号柱。
和\(1\)一样。
这三步总次数为\(2*f(i)+2^{n-i}-1\)。
解法就很显然了
\(f(n)=\min{\{2*f(i)+2^{n-i}-1\}}\)
枚举\(i\)，递归或者递推求解\(f(n)\)即可。
时间复杂度\(O(n^2+T)\)
\(T\)为数据组数，\(n\)为盘子数目。
最近点对问题
易得，答案为最近点对的距离除以\(2\)。
先把所有点按\(x\)从小到大排序，然后开始分治。
以\(x\)的中位数将点分为左右两半(我偷懒没用中位数)。分别求出两半内部的最近点对距离\(d_1\),\(d_2\)后，将左右两半按照\(y\)从小到大做归并排序(如果使用sort的话时间复杂度会多\(O(logn)\)，但是也许也能通过)。将左右两半距离中线小于等于\(min{d_1,d_2}\)的点拿出来，枚举左边的点，找到它对应的右边的\(6\)个点(证明见课本)。更新最近点对距离即可。
时间复杂度\(O(Tnlogn)\)
\(T\)为数据组数，\(n\)为点的数量。
求最小公倍数。
有个公式：\(LCM*GCD=a*b\)
两数之积等于最小公倍数与最大公因数之积。
用辗转相除法(更相减损术，欧几里得算法)求两数的最大公因数即可求出最小公倍数。
时间复杂度\(O(Tlogn)\)
\(T\)为数据组数，\(n\)为数字大小。
将所有\(5\)看成空格，将所有数排序。
用什么方法都行，把所有数提取出来，排序即可。
时间复杂度\(O(T(L+nlogn))\)
\(T\)为数据组数，\(L\)为字符串长度，\(n\)为数字个数。
每个字符串的权值是它的逆序对个数，将所有字符串按照权值从小到大排序输出。
首先求出每个字符串的逆序对个数，此题数据量小，字符集也很小，暴力\(O(n^2)\)就可以，预处理每个字符个数的前缀和之后再统计可以做到\(O(n)\)。
时间复杂度\(O(Tnmlogm)\)
\(T\)为数据组数，\(n\)为字符串长度，\(m\)为字符串个数。
类斐波那契数列。
结合题意和样例即可推出公式\(f(i)=f(i-3)+f(i-1)\)。
时间复杂度\(O(T+n)\)
\(T\)为数据组数，\(n\)为年数。
缩位：将一个数字变为它的所有数位相加。求\(n^n\)一直缩位最后变成的一位数。
实测发现万进制高精度也会超时。
(我使用的是高精度乘单精度，没有使用快速幂；如果使用快速幂的话需要把乘法改为高精度乘高精度，时间复杂度并没有变优秀)
据说有个什么\(9\)余数定理。实际上没必要，把一些小数据算出来之后就会发现一个很显然的规律。具体规律见代码(超时的做法没有删掉)。
时间复杂度\(O(T)\)
\(T\)为数据组数。
求一个区间内的所有回文素数。注意两个端点不一定按照升序给出。
先将所有回文素数预处理出来。如何预处理：枚举回文数的位数，dfs搜索这个回文数的半段(注意避免前导\(0\))，找到之后判断这个数是否是素数(不能预处理素数，空间不够)。询问时二分找到左端点，循环到右端点输出即可。
时间复杂度\(O(Tlogn+m)\)
\(T\)为数据组数，\(n\)为回文素数数量(不到\(800\))，m为回文数数量(不到\(10^5\))。
求\(a\times b\)
这……难顶。
高精度乘法会超时，需要快速傅里叶变换(FFT)，我不会，只会套模板，再见。
时间复杂度\(O(Tnlogn)\)
\(T\)为数据组数，\(n\)为数字长度。
汉诺塔问题，给出盘子数量，就第\(k\)次移动是什么。
汉诺塔问题可以分成三段：
当前目标为把\(n\)个盘从\(1\)号柱移动到\(3\)号柱。
1.把上面\(n-1\)个盘移动到\(2\)号柱。\(2^{n-1}-1\)次。
2.把剩下的\(1\)个盘移动到\(3\)号柱。\(1\)次。
3.把2号柱上\(n-1\)个盘移动到\(3\)号柱。\(2^{n-1}-1\)次。
判断第\(k\)次移动属于哪一步，递归判断直到边界即可。
时间复杂度\(O(Tn)\)
\(T\)为数据组数，\(n\)为盘子数。
只能交换相邻元素，求最少多少次交换能让这个数组变成升序。
从逆序对的角度考虑，每次交换一定会产生/消除一个逆序对。终状态是\(0\)个逆序对，因此我们要做到每次交换消除一个逆序对。
那么最终答案就等于逆序对个数。
经典问题逆序对个数，可以用归并排序或者离散化+树状数组求解。
我的代码是树状数组做法，树状数组是一个能够 修改+维护前缀和 的数据结构。
时间复杂度\(O(Tnlogn)\)
\(T\)为数据组数，\(n\)为数字个数。
代码合集：
//1001
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=(xx<<3)+(xx<<1)+ch-'0';ch=getchar();}
return xx*ff;
}
int T;
char s1[1010],s2[1010];
struct bignum{
int num[1010];
int len;
void clear()
{memset(num,0,sizeof(num)),len=1;}
bignum friend operator+(const bignum&A,const bignum&B){
bignum C;
C.clear();
C.len=B.len;
if(A.len>B.len)
C.len=A.len;
for(int i=1;i<=C.len;i++){
C.num[i]+=A.num[i]+B.num[i];
if(C.num[i]>=10){
C.num[i+1]++;
C.num[i]-=10;
}
}
if(C.num[C.len+1])
C.len++;
return C;
}
void print(){
for(int i=len;i>=1;i--)
printf("%d",num[i]);
}
}ans;
bignum s_to_b(char *s){
bignum lzh;
lzh.clear();
int len=strlen(s);
lzh.len=len;
for(int i=0;i<len;i++)
lzh.num[len-i]=s[i]-'0';
return lzh;
}
int main(){
//freopen("in","r",stdin);
//freopen("out","w",stdout);
T=read();
for(int I=1;I<=T;I++){
if(I!=1)
puts("");
scanf("%s %s",&s1,&s2);
ans=s_to_b(s1)+s_to_b(s2);
printf("Case %d:\n",I);
printf("%s + %s = ",s1,s2);
ans.print();
puts("");
}
return 0;
}
//1002
#include<cstdio>
#include<algorithm>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
const int maxn=10010;
int sum[maxn];
bool check(int x){
int sum=0;
for(int i=1;i*i<=x;i++)
if(x%i==0){
sum+=i;
if(i*i!=x)
sum+=x/i;
}
return sum==x*2;
}
int main(){
//freopen("in","r",stdin);
for(int i=1;i<maxn;i++)
sum[i]=sum[i-1]+check(i);
for(int _=read();_;_--){
int L=read(),R=read();
if(L>R)
swap(L,R);
printf("%d\n",sum[R]-sum[L-1]);
}
return 0;
}
//1003
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
const int MOD=9973;
int N,K;
struct matrix{
int num[10][10];
matrix(){
memset(num,0,sizeof(num));
}
void atom(){
memset(num,0,sizeof(num));
for(int i=0;i<N;i++)
num[i][i]=1;
}
void read_in(){
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
num[i][j]=read();
}
matrix friend operator*(const matrix&A,const matrix&B){
matrix C;
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
for(int k=0;k<N;k++)
(C.num[i][j]+=A.num[i][k]*B.num[k][j])%=MOD;
return C;
}
};
matrix qpow(matrix A,int p){
matrix ret;
ret.atom();
while(p){
if(p&1)
ret=ret*A;
A=A*A;
p>>=1;
}
return ret;
}
int main(){
//freopen("in","r",stdin);
for(int _=read();_;_--){
N=read(),K=read();
matrix mat;
mat.read_in();
mat=qpow(mat,K);
int sum=0;
for(int i=0;i<N;i++)
(sum+=mat.num[i][i])%=MOD;
printf("%d\n",sum);
}
return 0;
}
//1004
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=(xx<<3)+(xx<<1)+ch-'0';ch=getchar();}
return xx*ff;
}
inline void myswap(int&xx,int&yy)
{xx^=yy,yy^=xx,xx^=yy;}
int M,N,ans1,ans2;
int main(){
//freopen("in","r",stdin);
//freopen("out","w",stdout);
while(scanf("%d%d",&M,&N)!=EOF){
if(M>N)
myswap(M,N);
ans1=ans2=0;
for(int i=M;i<=N;i++)
if(i&1)
ans2+=i*i*i;
else
ans1+=i*i;
printf("%d %d\n",ans1,ans2);
}
return 0;
}
//1005
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int f[70];
int main(){
//freopen("in","r",stdin);
memset(f,10,sizeof(f));
f[0]=0,f[1]=1,f[2]=3;
for(int i=3;i<=64;i++)
for(int j=i;j>=0;j--){
if((1<<(i-j))-1>f[i])
break;
f[i]=min(f[i],2*f[j]+(1<<(i-j))-1);
}
int n;
while(scanf("%d",&n)!=EOF)
printf("%d\n",f[n]);
return 0;
}
//1006
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<utility>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
const int maxn=100010;
const double INF=1e18;
int N;
pair<double,double>p[maxn],tmp[maxn],a[maxn],b[maxn];
inline double sqr(const double&x){
return x*x;
}
inline double dis(const pair<double,double>&A,const pair<double,double>&B){
return sqrt(sqr(A.first-B.first)+sqr(A.second-B.second));
}
double DAC(int L,int R){
if(L==R)return INF;
int mid=(L+R)/2;
double M=p[mid].first;
double d=min(DAC(L,mid),DAC(mid+1,R));
int i=L,j=mid+1,k=L-1,cnta=0,cntb=0;
while(i<=mid&&j<=R){
if(p[i].second<=p[j].second){
tmp[++k]=p[i++];
if(M-tmp[k].first<=d)
a[++cnta]=tmp[k];
}
else{
tmp[++k]=p[j++];
if(tmp[k].first-M<=d)
b[++cntb]=tmp[k];
}
}
while(i<=mid){
tmp[++k]=p[i++];
if(M-tmp[k].first<=d)
a[++cnta]=tmp[k];
}
while(j<=R){
tmp[++k]=p[j++];
if(tmp[k].first-M<=d)
b[++cntb]=tmp[k];
}
for(int k=L;k<=R;k++)
p[k]=tmp[k];
for(i=1,j=1;i<=cnta;i++){
while(b[j].second<a[i].second&&dis(a[i],b[j])>d)
j++;
for(k=j;k<j+6&&k<=cntb;k++)
d=min(d,dis(a[i],b[k]));
}
return d;
}
int main(){
//freopen("in","r",stdin);
while(1){
N=read();
if(!N)break;
for(int i=1;i<=N;i++)
scanf("%lf%lf",&p[i].first,&p[i].second);
sort(p+1,p+1+N);
printf("%.2lf\n",DAC(1,N)/2);
}
return 0;
}
//1007
#include<cstdio>
using namespace std;
int gcd(int x,int y){
if(!y)return x;
return gcd(y,x%y);
}
int main(){
//freopen("in","r",stdin);
int n,m;
while(scanf("%d%d",&n,&m)!=EOF){
int GCD=gcd(n,m);
int LCM=n*m/GCD;
printf("%d\n",LCM);
}
return 0;
}
//1008
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=(xx<<3)+(xx<<1)+ch-'0';ch=getchar();}
return xx*ff;
}
char s[1010];
int len,a[610],tp,temp;
int main(){
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
while(scanf("%s",&s)!=EOF){
len=strlen(s);
s[len]='5';
tp=0;temp=0;
int i=0;
while(s[i]=='5')
i++;
for(;i<=len;i++){
if(s[i]!='5')
temp=temp*10+s[i]-'0';
else{
a[++tp]=temp,temp=0;
while(s[i+1]=='5')
i++;
}
}
sort(a+1,a+1+tp);
for(int i=1;i<tp;i++)
printf("%d ",a[i]);
printf("%d\n",a[tp]);
}
return 0;
}
//1009
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
char one(){
char ch=getchar();
while(ch==' '||ch=='\n')
ch=getchar();
return ch;
}
const int maxn=51,maxm=105;
int N,M,id[maxm],inv[maxn];
int s[maxm][maxn],sum[maxm][maxn][5];
inline bool cmp(const int&A,const int&B){
return inv[A]<inv[B];
}
inline int char_to_int(char ch){
if(ch=='A')return 1;
else if(ch=='C')return 2;
else if(ch=='G')return 3;
return 4;
}
inline char int_to_char(int c){
if(c==1)return 'A';
else if(c==2)return 'C';
else if(c==3)return 'G';
return 'T';
}
int main(){
//freopen("in","r",stdin);
for(int _=read();_;_--){
M=read(),N=read();
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++){
char ch=one();
s[i][j]=char_to_int(ch);
}
for(int i=1;i<=N;i++){
id[i]=i,inv[i]=0;
for(int k=1;k<=4;k++)
sum[i][M+1][k]=0;
for(int j=M;j>=1;j--)
for(int k=1;k<=4;k++)
sum[i][j][k]=sum[i][j+1][k]+(s[i][j]==k);
for(int j=1;j<=M;j++)
for(int k=1;k<s[i][j];k++)
inv[i]+=sum[i][j][k];
}
stable_sort(id+1,id+1+N,cmp);
for(int i=1;i<=N;i++){
for(int j=1;j<=M;j++)
printf("%c",int_to_char(s[id[i]][j]));
puts("");
}
if(_!=1)puts("");
}
return 0;
}
//1010
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
bool isprime(int x){
for(int i=2;i*i<=x;i++)
if(!(x%i))
return 0;
return 1;
}
const int maxn=60;
long long ans[maxn]={0,1,2,3};
int main(){
//freopen("in","r",stdin);
//freopen("out","w",stdout);
for(int i=4;i<maxn;i++)
ans[i]=ans[i-3]+ans[i-1];
while(1){
int n=read();
if(!n)break;
printf("%I64d\n",ans[n]);
}
return 0;
}
//1011
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
/*
const int MOD=10000;
struct big{
int num[3000],len;
big(){
memset(num,0,sizeof(num));
len=1;
}
bool friend operator<(const big&A,const big&B){
if(A.len!=B.len)
return A.len<B.len;
for(int i=A.len;i>=1;i--)
if(A.num[i]<B.num[i])
return 1;
else if(A.num[i]>B.num[i])
return 0;
return 0;
}
bool friend operator==(const big&A,const big&B){
if(A.len!=B.len)
return 0;
for(int i=1;i<=A.len;i++)
if(A.num[i]!=B.num[i])
return 0;
return 1;
}
big friend operator+(const big&A,const big&B){
big C;
C.len=max(A.len,B.len);
for(int i=1;i<=C.len;i++){
C.num[i]+=A.num[i]+B.num[i];
int k=i;
while(C.num[k]>=MOD){
C.num[k+1]+=C.num[k]/MOD;
C.num[k]%=MOD;
k++;
if(k>C.len)
C.len=k;
}
}
return C;
}
big friend operator-(big A,big B){
for(int i=1;i<=A.len;i++){
A.num[i]-=B.num[i];
int k=i;
while(A.num[k]<0){
A.num[k+1]--;
A.num[k]+=MOD;
k++;
}
}
while(A.len&&!A.num[A.len])
A.len--;
return A;
}
big friend operator*(big A,int B){
big C;
C.len=A.len;
for(int i=1;i<=A.len;i++){
C.num[i]+=A.num[i]*B;
int k=i;
while(C.num[k]>=MOD){
C.num[k+1]+=C.num[k]/MOD;
C.num[k]%=MOD;
k++;
if(k>C.len)
C.len=k;
}
}
return C;
}
void print(){
printf("%d",num[len]);
for(int i=len-1;i>=1;i--)
printf("%04d",num[i]);
}
int calc(){
int ret=0;
for(int i=1;i<=len;i++){
int t=num[i];
for(int j=1;j<=4;j++){
ret+=t%10;
t/=10;
}
}
return ret;
}
}zero;
big trans(char s[]){
int len=strlen(s);
big C;
for(int i=len-1;i>=0;i-=4){
for(int j=max(i-3,0);j<=i;j++)
C.num[C.len]=C.num[C.len]*10+s[j]-'0';
C.len++;
}
C.len--;
return C;
}
int calc(int x){
int ret=0;
while(x){
ret+=x%10;
x/=10;
}
return ret;
}
char str[10];
*/
int main(){
//freopen("in","r",stdin);
//freopen("out","w",stdout);
/*for(int i=1;i<=10000;i++)
printf("%d\n",i);*/
/*while(1){
scanf("%s",str);
int N=0;
for(int i=0;str[i];i++)
N=N*10+str[i]-'0';
if(!N)break;
big b=trans(str);
for(int i=1;i<N;i++)
b=b*N;
int ans=b.calc();
while(ans>=10)
ans=calc(ans);
printf("%d,",ans);
}*/
while(1){
int n=read();
if(!n)break;
if(n%3==0)puts("9");
else if(n%3==1){
n/=3;
if(n%3==0)puts("1");
else if(n%3==1)puts("4");
else puts("7");
}
else{
n/=3;
if(n%6==0)puts("4");
else if(n%6==1)puts("2");
else if(n%6==2)puts("1");
else if(n%6==3)puts("5");
else if(n%6==4)puts("7");
else puts("8");
}
}
return 0;
}
//1012
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
bool isprime(int x){
for(int i=2;i*i<=x;i++)
if(!(x%i))
return 0;
return 1;
}
int ans[800],cnt;
void dfs(int x,int n,int v){
if(x>n/2+n%2){
int t=v;
if(n&1)
t/=10;
while(t){
v=v*10+t%10;
t/=10;
}
if(isprime(v))
ans[++cnt]=v;
return;
}
for(int i=0;i<=9;i++)
if(!(x==1&&i==0))
dfs(x+1,n,v*10+i);
}
int main(){
//freopen("in","r",stdin);
//freopen("out","w",stdout);
for(int i=1;i<=8;i++)
dfs(1,i,0);
int L,R;
while(scanf("%d%d",&L,&R)!=EOF){
if(L>R)swap(L,R);
int p=lower_bound(ans+1,ans+1+cnt,L)-ans;
while(p<=cnt&&ans[p]<=R)
printf("%d\n",ans[p++]);
puts("");
}
return 0;
}
//1013
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<complex>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=(xx<<3)+(xx<<1)+ch-'0';ch=getchar();}
return xx*ff;
}
const int maxn=(1<<18)+1;
const double PI=acos(-1.0);
typedef complex<double> C;
int N,M,L,R[maxn];
C a[maxn],b[maxn];
void FFT(C a[],int arg){
for(int i=0;i<N;i++)
if(i<R[i])
swap(a[i],a[R[i]]);
for(int i=1;i<N;i<<=1){
C wn(cos(PI/i),arg*sin(PI/i));
for(int p=i<<1,j=0;j<N;j+=p){
C w(1,0);
for(int k=0;k<i;k++,w*=wn){
C x=a[j+k],y=w*a[j+k+i];
a[j+k]=x+y,a[j+k+i]=x-y;
}
}
}
}
char s1[50010],s2[50010];
int ans[100010];
int main(){
//freopen("in","r",stdin);
while(scanf("%s",s1)!=EOF){
scanf("%s",s2);
N=strlen(s1)-1,M=strlen(s2)-1;
for(int i=0;i<=N;i++)
a[i]=s1[N-i]-'0';
for(int i=0;i<=M;i++)
b[i]=s2[M-i]-'0';
M+=N;
for(N=1;N<=M;N<<=1)
L++;
for(int i=0;i<N;i++)
R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));
FFT(a,1);FFT(b,1);
for(int i=0;i<=N;i++)
a[i]*=b[i];
FFT(a,-1);
for(int i=M;i>=0;i--)
ans[i]=(int)(a[i].real()/N+0.5);
int k;
for(k=0;k<=M||ans[k];k++)
if(ans[k]>=10)
ans[k+1]+=ans[k]/10,ans[k]%=10;
while(!ans[k]&&k>0)
k--;
for(int i=k;i>=0;i--)
printf("%d",ans[i]);
puts("");
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(R,0,sizeof(R));
memset(ans,0,sizeof(ans));
L=0;
}
return 0;
}
//1014
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
long long READ(){
long long xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
int N;
long long K;
inline int diff(int x,int y){
if(x!=1&&y!=1)return 1;
if(x!=2&&y!=2)return 2;
return 3;
}
void dfs(int x,long long k,int a,int b){
int c=diff(a,b);
if(k<=(1LL<<x-1)-1)
dfs(x-1,k,a,c);
else{
k-=(1LL<<x-1)-1;
if(k==1)
printf("%d %d %d\n",x,a,b);
else
dfs(x-1,k-1,c,b);
}
}
int main(){
//freopen("in","r",stdin);
for(int _=read();_;_--){
N=read(),K=READ();
dfs(N,K,1,3);
}
return 0;
}
//1015
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
const int maxn=1000010;
int N,a[maxn],b[maxn];
struct BIT{
int b[maxn];
int lowbit(int x){
return x&-x;
}
void clear(){
for(int i=0;i<=N;i++)
b[i]=0;
}
void upd(int x,int d){
for(;x<=N;x+=lowbit(x))
b[x]+=d;
}
int query(int x){
int ret=0;
for(;x;x-=lowbit(x))
ret+=b[x];
return ret;
}
}bit;
int main(){
//freopen("in","r",stdin);
//freopen("out","w",stdout);
while(scanf("%d",&N)!=EOF){
for(int i=1;i<=N;i++)
a[i]=b[i]=read();
sort(b+1,b+1+N);
for(int i=1;i<=N;i++)
a[i]=lower_bound(b+1,b+1+N,a[i])-b;
long long ans=0;
for(int i=N;i>=1;i--){
ans+=bit.query(a[i]);
bit.upd(a[i],1);
}
printf("%I64d\n",ans);
bit.clear();
}
return 0;
}手机扫一扫
移动阅读更方便
你可能感兴趣的文章