2014ブルーブリッジ国試合C組

11765 ワード

タイトル:序数の整列
a b c dという4文字で1つの列を構成すると、4!=24種類で、シーケンスを並べた場合、各列は1つのシーケンス番号に対応します.
  abcd  0
  abdc  1
  acbd  2
  acdb  3
  adbc  4
  adcb  5
  bacd  6
  badc  7
  bcad  8
  bcda  9
  bdac  10
  bdca  11
  cabd  12
  cadb  13
  cbad  14
  cbda  15
  cdab  16
  cdba  17
  ...
今では10個以上の2つの異なる小文字があり、それらからなる列を与えていますが、この列のすべての配列のシーケンス番号を求めることができますか?
【入力形式】
1行、1列.
【出力形式】
文字列のすべての配列で生成された列のシーケンス番号を表す整数行.注意:最小のシーケンス番号は0です.
例:
入力:
bdca
プログラムは出力するべきです:
11
次に例を示します.
入力:
cedab
プログラムは出力するべきです:
70
#include
using namespace std;
char s[12],str[12];
int main()
{
	scanf("%s",s);
	int len=strlen(s);
	for(int i=0;i

1 e 5データの作り方:set+ツリー配列
#include
using namespace std;
typedef long long ll;
#define lowbit(x) x&(-x)
const int N=1e5+10; 
char s[N],str[N],len;
ll f[N];
set st;
int sum[N];
void add(int pos,int val)
{
	while(pos<=len)
	{
		sum[pos]+=val;
		pos+=lowbit(pos);
	}
}
int query(int pos)
{
	int res=0;
	while(pos)
	{
		res+=sum[pos];
		pos-=lowbit(pos);
	}
	return res;
}
int main()
{
	f[0]=1;
	for(int i=1;i<=10;i++)
		f[i]=f[i-1]*i;
	scanf("%s",s);
	len=strlen(s);
	for(int i=0;i

べき乗行列:
atmはべき乗ゼロ行列を満たさず、彼自身はべき乗1行列を想定した:1つの方程式Mに対して、正の整数kがM^k=Iを満たす場合、Iが単位行列である場合、Mはべき乗1行列である.
 
atmは特に、行ごとに1列ずつあり、1つしかない方陣に夢中になっている.atmの絶え間ない実験を経て,彼はこの行列がべき乗一行列であることを発見した.
 
今、彼の問題は、以上の条件を満たす方程式を与えて、彼は最小のkがいくらであるかを求めたいということです.
 
【入力形式】
1行目の正の整数nは、マトリクスサイズがn*nであることを示す.
次にn行目、各行の2つの正の整数i jは、行列のi行目j列が1であることを示す.
1 <= i, j <= n .
行番号、列番号はすべて1から始まります.
 
【出力形式】
1行です.正の整数、すなわちテーマで言う最小のk.
 
【サンプル入力】
5
3 1
1 2
4 4
2 3
5 5
 
【サンプル出力】
3
 
【データ範囲】
30%のデータに対してn<=10を満たす
60%のデータに対して10^18を超えない
100%のデータに対してn<=10000を満たす
 
すべての到着(i,i)の位置の回数の最小の公倍数を求めます
60%:
#include
using namespace std;
int v1[10010];
int n;
int main()
{
    scanf("%d",&n);
    int x,y;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&x,&y);
        v1[x]=y;
    }
    long long ans=1;
    long long cnt;
    for(int i=1;i<=n;i++)
    {
        cnt=1;
        x=v1[i];
        while(x!=i)
        {
            cnt++;
            x=v1[x];    
        } 
    //  cout<

最大100%
#include
using namespace std; 
 
#define MAXN 9999
#define MAXSIZE 10
#define DLEN 4
 
class BigNum
{ 
private: 
	int a[500];    //          
	int len;       //    
public: 
	BigNum(){ len = 1;memset(a,0,sizeof(a)); }   //    
	BigNum(const int);       //   int          
	BigNum(const char*);     //                
	BigNum(const BigNum &);  //      
	BigNum &operator=(const BigNum &);   //       ,          
 
	friend istream& operator>>(istream&,  BigNum&);   //       
	friend ostream& operator<(const BigNum & T)const;   //             
	bool   operator>(const int & t)const;      //     int          
	bool   operator==(const BigNum & T)const;  //          
	bool   operator==(const int & t)const;     //    int       
 
	void print();       //    
}; 
BigNum::BigNum(const int b)     //   int          
{ 
	int c,d = b;
	len = 0;
	memset(a,0,sizeof(a));
	while(d > MAXN)
	{
		c = d - (d / (MAXN + 1)) * (MAXN + 1); 
		d = d / (MAXN + 1);
		a[len++] = c;
	}
	a[len++] = d;
}
BigNum::BigNum(const char*s)     //                
{
	int t,k,index,l,i;
	memset(a,0,sizeof(a));
	l=strlen(s);   
	len=l/DLEN;
	if(l%DLEN)
		len++;
	index=0;
	for(i=l-1;i>=0;i-=DLEN)
	{
		t=0;
		k=i-DLEN+1;
		if(k<0)
			k=0;
		for(int j=k;j<=i;j++)
			t=t*10+s[j]-'0';
		a[index++]=t;
	}
}
BigNum::BigNum(const BigNum & T) : len(T.len)  //      
{ 
	int i; 
	memset(a,0,sizeof(a)); 
	for(i = 0 ; i < len ; i++)
		a[i] = T.a[i]; 
} 
BigNum & BigNum::operator=(const BigNum & n)   //       ,          
{
	int i;
	len = n.len;
	memset(a,0,sizeof(a)); 
	for(i = 0 ; i < len ; i++) 
		a[i] = n.a[i]; 
	return *this; 
}
istream& operator>>(istream & in,  BigNum & b)   //       
{
	char ch[MAXSIZE*4];
	int i = -1;
	in>>ch;
	int l=strlen(ch);
	int count=0,sum=0;
	for(i=l-1;i>=0;)
	{
		sum = 0;
		int t=1;
		for(int j=0;j<4&&i>=0;j++,i--,t*=10)
		{
			sum+=(ch[i]-'0')*t;
		}
		b.a[count]=sum;
		count++;
	}
	b.len =count++;
	return in;
 
}
ostream& operator<= 0 ; i--)
	{ 
		cout.width(DLEN); 
		cout.fill('0'); 
		cout << b.a[i]; 
	} 
	return out;
}
 
BigNum BigNum::operator+(const BigNum & T) const   //           
{
	BigNum t(*this);
	int i,big;      //     
	big = T.len > len ? T.len : len; 
	for(i = 0 ; i < big ; i++) 
	{ 
		t.a[i] +=T.a[i]; 
		if(t.a[i] > MAXN) 
		{ 
			t.a[i + 1]++; 
			t.a[i] -=MAXN+1; 
		} 
	} 
	if(t.a[big] != 0)
		t.len = big + 1; 
	else
		t.len = big;   
	return t;
}
BigNum BigNum::operator-(const BigNum & T) const   //            
{  
	int i,j,big;
	bool flag;
	BigNum t1,t2;
	if(*this>T)
	{
		t1=*this;
		t2=T;
		flag=0;
	}
	else
	{
		t1=T;
		t2=*this;
		flag=1;
	}
	big=t1.len;
	for(i = 0 ; i < big ; i++)
	{
		if(t1.a[i] < t2.a[i])
		{ 
			j = i + 1; 
			while(t1.a[j] == 0)
				j++; 
			t1.a[j--]--; 
			while(j > i)
				t1.a[j--] += MAXN;
			t1.a[i] += MAXN + 1 - t2.a[i]; 
		} 
		else
			t1.a[i] -= t2.a[i];
	}
	t1.len = big;
	while(t1.a[t1.len - 1] == 0 && t1.len > 1)
	{
		t1.len--; 
		big--;
	}
	if(flag)
		t1.a[big-1]=0-t1.a[big-1];
	return t1; 
} 
 
BigNum BigNum::operator*(const BigNum & T) const   //            
{ 
	BigNum ret; 
	int i,j,up; 
	int temp,temp1;   
	for(i = 0 ; i < len ; i++)
	{ 
		up = 0; 
		for(j = 0 ; j < T.len ; j++)
		{ 
			temp = a[i] * T.a[j] + ret.a[i + j] + up; 
			if(temp > MAXN)
			{ 
				temp1 = temp - temp / (MAXN + 1) * (MAXN + 1); 
				up = temp / (MAXN + 1); 
				ret.a[i + j] = temp1; 
			} 
			else
			{ 
				up = 0; 
				ret.a[i + j] = temp; 
			} 
		} 
		if(up != 0) 
			ret.a[i + j] = up; 
	} 
	ret.len = i + j; 
	while(ret.a[ret.len - 1] == 0 && ret.len > 1)
		ret.len--; 
	return ret; 
} 
BigNum BigNum::operator/(const int & b) const   //             
{ 
	BigNum ret; 
	int i,down = 0;   
	for(i = len - 1 ; i >= 0 ; i--)
	{ 
		ret.a[i] = (a[i] + down * (MAXN + 1)) / b; 
		down = a[i] + down * (MAXN + 1) - ret.a[i] * b; 
	} 
	ret.len = len; 
	while(ret.a[ret.len - 1] == 0 && ret.len > 1)
		ret.len--; 
	return ret; 
}
int BigNum::operator %(const int & b) const    //     int               
{
	int i,d=0;
	for (i = len-1; i>=0; i--)
	{
		d = ((d * (MAXN+1))% b + a[i])% b;  
	}
	return d;
}
BigNum BigNum::operator^(const int & n) const    //   n    
{
	BigNum t,ret(1);
	int i;
	if(n<0)
		exit(-1);
	if(n==0)
		return 1;
	if(n==1)
		return *this;
	int m=n;
	while(m>1)
	{
		t=*this;
		for( i=1;i<<1<=m;i<<=1)
		{
			t=t*t;
		}
		m-=i;
		ret=ret*t;
		if(m==1)
			ret=ret*(*this);
	}
	return ret;
}
bool BigNum::operator>(const BigNum & T) const   //             
{ 
	int ln; 
	if(len > T.len)
		return true; 
	else if(len == T.len)
	{ 
		ln = len - 1; 
		while(a[ln] == T.a[ln] && ln >= 0)
			ln--; 
		if(ln >= 0 && a[ln] > T.a[ln])
			return true; 
		else
			return false; 
	} 
	else
		return false; 
}
bool BigNum::operator >(const int & t) const    //     int          
{
	BigNum b(t);
	return *this>b;
}
bool BigNum::operator==(const BigNum & T) const  //          
{
	if(len != T.len) return false;
	for(int i = 0; i < len; i++)
	{
		if(a[i] != T.a[i])	return false;
	}
	return true;
} 
bool BigNum::operator==(const int & t) const  //    int          
{
	BigNum b(t);
	return *this==b;
}
void BigNum::print()    //    
{ 
	int i;   
	cout << a[len - 1]; 
	for(i = len - 2 ; i >= 0 ; i--)
	{ 
		cout.width(DLEN); 
		cout.fill('0'); 
		cout << a[i]; 
	} 
	cout << endl;
}

int v1[10010];
int n;
int main()
{
//	cout<<1<

タイトル:繰り返しモード
 
drdの親友として、技術男atmはdrdの誕生日に超長文字列Sをプレゼントした.atmはdrdにその中で最も長い文字列Tを見つけて、TがSの中で少なくとも2回現れたようにしなければならないが、彼が言いたい秘密はTの中に隠されている.
 
文字列が長すぎるため、drdはいつも適切なTが見つからない.そこでdrdは彼にこのTの長さを見つけてください.
 
【入力形式】
1行です.1つの文字列、すなわちテーマの中で言うS.
 
【出力形式】
1行です.最も長いTの長さを表す整数.
 
【サンプル入力】
ababa
 
【サンプル出力】
3
 
「データ範囲」
30%のデータに対して、S長<=100
60%のデータに対して、S長<=8000
100%のデータに対して、S長<=500000
n^4:
#include
using namespace std;
string s;
int main()
{
	cin>>s;
	int ans=0;
	int len=s.size();
	for(int i=0;i

n^3:
//  400
#include
using namespace std;
string s;
int nex[1010];
int len;
void getnex(int l,int r)
{
	int i=l,j=-1;
	nex[i]=-1;
	while(i<=r)
	{
		if(j==-1 || s[i]==s[j])
		{
			if(j==-1)
			{
				i++,j=l;
				nex[i]=j;
			}
			else nex[++i]=++j;
		}
		else j=nex[j];
	}
}
int solve(int l,int r,int pos)
{
	int i=l,j=pos;
	while(j>s;
	int ans=0;
	len=s.size();
	for(int i=0;i

n^2log(n):
// 1000
#include
using namespace std;
string s[50010];
string str;
int main()
{
	cin>>str;
	int len=str.size();
	string cnt="";
	for(int i=len-1;i>=0;i--)
	{
		cnt=(char)str[i]+cnt;
		s[i]=cnt;
	}
	sort(s,s+len);
	int ans=0;
	int l;
	for(int i=1;i

n^2:
// 10000
#include
using namespace std;
int len;
string s;
int main()
{
	cin>>s;
	len=s.size();
	int ans=0;
	int cnt;
	for(int i=1;i

nlog(n):
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int N=510000;
int t1[N],t2[N],sum[N],rk[N],ht[N],sa[N],str[N],n;
char s[N];
void get_sa(int n,int m)
{
	int *x=t1,*y=t2;
	for(int i=0;i=0;i--) sa[--sum[x[i]]]=i;
	for(int p,j=1;p<=n;j<<=1)
	{
		p=0;
		for(int i=n-j;i=j) y[p++]=sa[i]-j;
		for(int i=0;i=0;i--) sa[--sum[x[y[i]]]]=y[i];
		swap(x,y);
		p=1;
		x[sa[0]]=0;
		for(int i=1;i=n) break;
		m=p;
	}
	int k=0;n--;
	for(int i=0;i<=n;i++) rk[sa[i]]=i;
	for(int i=0;i