SGU 232

acm.sgu.ru/problem.php
算法不难想。。但因为各种各样的SB原因WA了N次。。主要是我是SB。。
很显然设d=(N,K),那么按题目的说法一共有d类。。每类长度都是N/d。。那么只要求出每类的最大值然后比较一下就可以知道全部的最大值了,而每类中那个很显然是个最大表示法的经典问题。。所以就OK了。。但是K太打了所以要用long long这玩意搞的我累死。。晕啊!
我决定了。。以后我不论什么变量都用long long。。TMD老子不要效率了。。
Code:
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
const int inf=~0U>>1,maxn=150000+1;
using namespace std;
int A[maxn],n;
typedef long long ll;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int get(ll i){return A[i%n];}
int main()
{
//freopen("in","r",stdin);
char c;int k,d,l;cin>>n>>k;k%=n;d=gcd(k,n),l=n/d;
scanf("n");rep(i,n)scanf("%c",&c),A[i]=c-‘0′;
int m=-1;
rep(a,d)
{
int i=0,j=1;ll t=0;
while(i<l&&j<l&&t<l)
{
int A=get(a+(i+t)*k),B=get(a+(j+t)*k);
if(A==B)t++;
else
{
if(A<B){i+=t+1;t=0;}
else{j+=t+1;t=0;}
if(i==j)j++;
}
}
t=a+min(i,j)*ll(k);t%=n;bool c;
if(m<0)c=true;
else rep(i,l)
{
int A=get(t+ll(i)*k),B=get(m+ll(i)*k);
if(A<B){c=false;break;}
if(A>B){c=true;break;}
}
if(c)m=t;
}
rep(i,n)printf("%d",get(m+ll(i)*k));
printf("n");
}

排序。。。

    我SB了。。。各位神牛WS我囧。。。。最近教一个同学排序于是就写了3个排序的基本算法。。我发现基数排序真是快的跟鬼一样。。。
快速排序:
#include <iostream>
#include <cstdlib>
#define rep(i,n) for(int i=0;i<n;i++)
const int inf=~0U>>1,maxn=10000000;
using namespace std;
int A[maxn];
void sort(int l,int r)
{
if(r-l<2)return;
int h=l,x=A[l+rand()%(r-l+1)];
for(int i=l;i<=r;i++)if(A[i]<x){int t=A[i];A[i]=A[h];A[h]=t;h++;}
sort(l,h-1);sort(h+1,r);
}
int main()
{
int n;cin>>n;rep(i,n)scanf("%d",A+i);sort(0,n-1);
}堆排序:
#include <cstdio>
#define rep(i,n) for(int i=0;i<n;i++)
const int inf=~0U>>1,maxn=10000000;
using namespace std;
int n,A[maxn];
inline int swap(int&a,int&b){a^=b^=a^=b;}
void Up(int i)
{
if(i/2&&A[i/2]>A[i])swap(A[i],A[i/2]),Up(i/2);
}
void Down(int i)
{
int p=i*2;if(p>n)return;
if(p+1<=n&&A[p+1]<A[p])++p;
if(A[i]>A[p])swap(A[i],A[p]),Down(p);
}
int main()
{
scanf("%d",&n);rep(i,n)scanf("%d",A+i+1),Up(i+1);
rep(i,n)swap(A[1],A[n–]),Down(1);
}基数排序(每4位):
#include <algorithm>
#include <cstdio>
#define rep(i,n) for(int i=0;i<n;i++)
const int inf=~0U>>2,maxn=1000000;
using namespace std;
int S0[maxn],S1[maxn],n,C[16]={};
int*A=S0,*B=S1;
int main()
{
scanf("%d",&n);rep(i,n)scanf("%d",A+i);
rep(x,4)
{
int d=x*4;rep(i,16)C[i]=0;
rep(i,n)C[(A[i]>>d)&15]++;rep(i,16)if(i)C[i]+=C[i-1];
for(int i=n-1;i>=0;i–)B[–C[(A[i]>>d)&15]]=A[i];
swap(A,B);
}
}无论从代码长度还是速度来说。。都是基数排序强。。囧啊。。

Page 4 of 41234