|
我叫張小黑
張小黑的掙扎生活 |
37 37 22 7
0 15 15 6
0 0 9 5
0 0 4 4
0 0 0 3
0 0 0 2
0 0 0 1
#include<iostream>
#include<algorithm>
using namespace std;
#define Max 35
__int64 num[Max],dice[Max];
bool cmp(__int64 a,__int64 b)
{
return a<b;
}
void solve(int n)
{
__int64 i,j;
for(i=1;i<=dice[n];i++)
num[i]=1;
for(i=n;i>=1;i--)
for(j=dice[i]-1;j>=0;j--)
num[j]+=num[j+1];
}
int main()
{
int n,i;
while(scanf("%d",&n)!=EOF&&n){
memset(dice,0,sizeof(dice));
memset(num,0,sizeof(num));
for(i=1;i<=n;i++)
scanf("%I64d",&dice[i]);
sort(dice+1,dice+n+1,cmp);
solve(n);
printf("%I64d\n",num[1]);
}
return 0;
}2008年4月10日23:52:47
第一個問題:
由平面中的n條直線確定的最大區域數Ln
Ln=Ln-1+n(n>0);
Ln=1+n*(n+1)/2;
第二個問題:
是平面直線的變形問題,用彎曲的線來代替直線,每一個彎曲線含有一個“鋸齒形的轉角”,同樣確定平面區域的最大個數Zn
(我們把一條彎曲折線抽象為兩條,但是合并了某些區域)
Zn=L2n-2*n=2*n*n-n+1;(n>=0);
第三個問題:
就是一下這個問題:
count the regions
若當前有n-1條邊,那么在往里面加一條邊,這條新加的邊最多和以前的邊有9*(n-1)個交點,
那么會添加 9*(n-1)+1個面
這條規律對于上面兩種也是用,加x個點,那么就會添加x+1個面
那么總結下來 Xn=Xn-1+9*(n-1)+1
即Xn=(9/2)*n*n-(7/2)*n+1;
以下是我的代碼:
#include<stdio.h>
int main()
{
long long n;
long long ans;
while(scanf("%lld",&n)!=EOF){
ans=9*n*n-7*n+2;
ans/=2;
printf("%lld\n",ans);
}
return 0;
}
#include<iostream>
#include<cstring>
#define keyNum 26
#define MaxN 500005
struct node{
int parent;
int rank;
int num;//這個顏色出現的次數
node()
{
num=rank=0;
parent=-1;
}
};
node colour[MaxN];
int id=0;//數組標記
struct trie{
struct trieNode{//trie結點的結構
trieNode *link[keyNum];//下標為 'a' , 'b' , 'c' , , 'z' 的指針數組
int num[keyNum];//插入這個單詞在數組中的位置
trieNode(){
memset(num,-1,sizeof(num));//-1表示還未插入數組
memset(link,NULL,sizeof(link));
}
void init(){
memset(link,NULL,sizeof(link));
memset(num,-1,sizeof(num));
}
};
trieNode* root;
trie()
{
root=(trieNode*)malloc(sizeof(trieNode));//初始化時為root申請了空間
root->init();
}
int Insert(char []);//返回數組中的位置
void Delete(trieNode*);//釋放空間
};
void trie::Delete(trieNode* t)
{
int i;
for(i=0;i<keyNum;i++)
if(t->link[i])Delete(t->link[i]);
memset(t->num,0,sizeof(t->num));
delete(t);
}
int trie::Insert(char x[])
{
trieNode *current=root;
int i=1;
while(x[i]){
if(current->link[x[i-1]-'a']==NULL){
current->link[x[i-1]-'a']=(trieNode*)malloc(sizeof(trieNode));
(current->link[x[i-1]-'a'])->init();
}
current=current->link[x[i-1]-'a'];
i++;
}
if(current->num[x[i-1]-'a']==-1)
current->num[x[i-1]-'a']=id++;
colour[current->num[x[i-1]-'a']].num++;//出現的次數++
return current->num[x[i-1]-'a'];
}
void init()
{
int i;
for(i=0;i<MaxN;i++)
colour[i].parent=i;
}
void union_set(int x,int y)
{
if(colour[x].rank>colour[y].rank)
colour[y].parent=x;
else {
colour[x].parent=y;
if(colour[x].rank==colour[y].rank)
colour[y].rank++;
}
}
int find_set(int x)
{
if(x!=colour[x].parent)
colour[x].parent=find_set(colour[x].parent);
return colour[x].parent;
}
bool comman_father()
{
int i,p=0;
p=find_set(0);
for(i=1;i<id;i++)
if(find_set(i)!=p)return false;
return true;
}
void solve()
{
if(comman_father()==false){
printf("Impossible\n");
return;
}
int i,head_end=0;
for(i=0;i<id;i++)
if(colour[i].num%2==1)//判斷頭和尾
head_end++;
if(head_end==2||!head_end)//一個沒回路,一個是有回路
printf("Possible\n");
else printf("Impossible\n");
}
int main()
{
char colr1[12],colr2[12];
trie a;
int ncolr1,ncolr2;
init();
while(scanf("%s%s",colr1,colr2)!=EOF){
ncolr1=a.Insert(colr1);
ncolr2=a.Insert(colr2);
union_set(find_set(ncolr1),find_set(ncolr2));
}
//下面判斷有幾個parent,若有多個失敗
solve();
a.Delete(a.root);
return 0
}
//SA-SB=kL(k為整數)
//SA=x+pm SB=y+pn
//(x-y)+p(m-n)=kL
//p(n-m)+kL=x-y
//ax+by=n<=>a'x+b'y=n/gcd(a,b)(此時a'與b'互質)
//若x0,y0為歐幾里得所得解
//x=x0+b't y=y0-a't
#include<iostream>
__int64 Ext_Euclid(__int64 a,__int64 b,__int64* x,__int64* y)
{
__int64 p,q,d;
if(a==0){*x=0;*y=1;return b;}
if(b==0){*x=1;*y=0;return a;}
d=Ext_Euclid(b,a%b,&p,&q);
*x=q;
*y=p-(a/b)*q;
return d;
}
int main()
{
/*freopen("1.IN","r",stdin);
freopen("my.OUT","w",stdout);*/
__int64 x,y,m,n,l;//x為A的起始點,y為B的起始點
//m為x的步長,n為y的步長,l為緯度長
__int64 c,a,d;
__int64 p,q;
while(scanf("%I64d%I64d%I64d%I64d%I64d",&x,&y,&m,&n,&l)!=EOF){
if(n==m)printf("Impossible\n");
else {
if(m>n){a=m-n;c=y-x;}
else {a=n-m;c=x-y;}
d=Ext_Euclid(a,l,&p,&q);
if((x>y?(x-y):(y-x))%d)printf("Impossible\n");
else {
p*=c/d;
while(p<0)p+=l/d;//這里錯了,最小的那個不是這么加的
p=p%l;
printf("%I64d\n",p);
}
}}
return 0;
}
#include<iostream>
#define MaxN 100005
char word[MaxN];
int data[MaxN],keys[MaxN];
typedef struct node{
int d;
int x;
int y;
void operator=(node b)
{
d=b.d;
x=b.x;
y=b.y;
}}NODE;
NODE EXTENDED_EUCLID(int a,int b)
{
NODE first,sec;
if(b==0){
sec.d=a;
sec.x=1;
sec.y=0;
return sec;
}
first=EXTENDED_EUCLID(b,(a%b+b)%b);
sec.d=first.d;
sec.x=first.y;
sec.y=first.x-(a/b)*first.y;
return sec;
}
int main()
{
int n,i;
node tmp;
while(scanf("%s",word)!=EOF){
memset(data,0,sizeof(data));
memset(keys,0,sizeof(keys));
int len=strlen(word);
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&data[i]);
for(i=0;i<n;i++)
scanf("%d",&keys[i]);
for(i=0;i<n;i++){
tmp=EXTENDED_EUCLID(data[i],keys[i]);
while(tmp.x<0)
tmp.x+=keys[i]/tmp.d;
printf("%c",word[tmp.x%len]);
}
printf("\n");
}
return 0;
}
#include<iostream>
#include<math.h>
#define MaxN 500005
#define M 987654321
int notP[MaxN];
using namespace std;
void init()
{
int i,j;
memset(notP,0,sizeof(notP));
notP[1]=1;
for(i=2;i<sqrt((double)MaxN);i++)
if(notP[i]==0){
for(j=2;j*i<MaxN;j++)
notP[j*i]=1;
}
}
int solve(int n)
{
int i,ans=1,t;
for(i=2;i<=n;i++){
if(notP[i])continue;
t=n;
while(t>=i){
ans=(((__int64)ans)*i)%M;
t/=i;
}
}
return ans;
}
int main()
{
int N,ans;
init();
while(scanf("%d",&N)!=EOF){
ans=solve(N);
printf("%d\n",ans);
}
return 0;
}
#include<iostream>
#include<cstring>
#define MaxN 100005
char deck[MaxN];
int main()
{
int numR,numS,i,k,remR,remS,len;
while(scanf("%s",deck)!=EOF){
remR=remS=numR=numS=k=0;
len=(int)strlen(deck);
for(i=0;i<len;i++){
if(deck[i]=='R')numR++;
else numS++;
if(numR-remR>numS-remS){
remR=numR;
remS=numS;
k=i+1;}
}
printf("%d\n",k);
}
return 0;
}
#include<iostream>
#define MaxS 23*100//每次最多丟到100
int sizeA[6],sizeB[6];
double pA[MaxS],pB[MaxS];
int numDiceA,numDiceB;
void compute(double p[],int size[],int numSize)
{
int i,j,t;
for(i=1;i<numSize;i++)
for(j=MaxS-1;j>=0;j--){
p[j]=0;//important
for(t=0;t<6;t++)
if(j-size[t]>0)
p[j]+=p[j-size[t]]/6.0;
}
}
int main()
{
int i;
double ans,tmp[MaxS];
while(scanf("%d%d",&numDiceA,&numDiceB)!=EOF){
ans=0.0;
memset(tmp,0,sizeof(tmp));
memset(pA,0,sizeof(pA));
memset(pB,0,sizeof(pB));
for(i=0;i<6;i++){
scanf("%d",&sizeA[i]);
pA[sizeA[i]]+=1/6.0;}
for(i=0;i<6;i++){
scanf("%d",&sizeB[i]);
pB[sizeB[i]]+=1/6.0;}
compute(pA,sizeA,numDiceA);
compute(pB,sizeB,numDiceB);
for(i=1;i<MaxS;i++)
tmp[i]=tmp[i-1]+pB[i-1];
for(i=1;i<MaxS;i++)
ans+=pA[i]*tmp[i];
printf("%.9lf\n",ans);
}
return 0;
}
#include<iostream>
#define keyNum 26
#define MaxN 50
struct trie{
struct trieNode{//trie結點的結構
trieNode *link[keyNum];//下標為 'A' , 'B' , 'C' ,
, 'Z' 的指針數組
int num[keyNum];//插入key的次數
trieNode(){
memset(num,0,sizeof(num));
memset(link,NULL,sizeof(link));
}
void init(){
memset(link,NULL,sizeof(link));
memset(num,0,sizeof(num));
}
};
trieNode* root;
trie()
{
root=(trieNode*)malloc(sizeof(trieNode));//初始化時為root申請了空間
root->init();
}
bool Search(char *);
void Insert(char []);
void Delete(trieNode*);
};
bool trie::Search(char * x)
{
if(*x==0)return false;
trieNode* current=root;
x++;
while(*x){
if(current->link[*(x-1)-'a'])
current=current->link[*(x-1)-'a'];
else break;
x++;
}
if(*x==0&¤t->num[*(x-1)-'a'])
return true;
else return false;
}
void trie::Delete(trieNode* t)
{
int i;
for(i=0;i<keyNum;i++)
if(t->link[i])Delete(t->link[i]);
memset(t->num,0,sizeof(t->num));
delete(t);
}
void trie::Insert(char x[])
{
trieNode *current=root;
int i=1;
while(x[i]){
if(current->link[x[i-1]-'a']==NULL){
current->link[x[i-1]-'a']=(trieNode*)malloc(sizeof(trieNode));
(current->link[x[i-1]-'a'])->init();
}
current=current->link[x[i-1]-'a'];
i++;
}
(current->num[x[i-1]-'a'])++;
}
char c[ 50000 ][MaxN],tmp;
int main()
{
trie a;
int i=0,j,num;
while(scanf("%s",c[i])!=EOF)
a.Insert(c[i++]);
num=i;
for(i=0;i<num;i++)
for(j=1;c[i][j];j++){
tmp=c[i][j];
c[i][j]=0;
if(a.Search(c[i])){
c[i][j]=tmp;
if(a.Search(&c[i][j])){
printf("%s\n",c[i]);
break;}
}
else c[i][j]=tmp;
}
a.Delete(a.root);
return 0;
}
#include<iostream>
using namespace std;
#define Max 200
#define Max_b 7
typedef struct bigint{
int data[Max];//從0開始存儲
int len;
int i;//表示小數位
bigint()
{
memset(data,0,sizeof(data));
len=1;
i=0;
}
friend bigint operator+(bigint,bigint);
friend bigint operator*(bigint,bigint);
void print();//小數點在第i位上,后面有i個小數位
void operator=(const bigint&y){
len=y.len;
for(int j=0;j<y.len;j++)
data[j]=y.data[j];
i=y.i;
}
}BIGINT;
BIGINT operator+(BIGINT x,BIGINT y)
{
BIGINT r;
int rlen=x.len>y.len?x.len:y.len;
int tmp,i,jinwei=0;
for(i=0;i<rlen;i++){
tmp=x.data[i]+y.data[i]+jinwei;
r.data[i]=tmp%10;
jinwei=tmp/10;}
if(jinwei)r.data[rlen++]=jinwei;
r.len=rlen;
return r;
}
BIGINT operator*(BIGINT x,BIGINT y)
{
BIGINT r;
int i,j;
memset(r.data,0,sizeof(r.data));
r.len=x.len+y.len;
for(i=0;i<x.len;i++)
for(j=0;j<y.len;j++)
r.data[i+j]+=x.data[i]*y.data[j];
for(i=0;i<r.len;i++){
r.data[i+1]+=r.data[i]/10;
r.data[i]%=10;}
while(r.data[i]){
r.data[i+1]+=r.data[i];
r.data[i]%=10;
i++;}
while(i>=0&&!r.data[i])i--;//這個已經消除了開頭的零
//末尾不存在零,不用考慮
if(i!=-1)r.len=i+1;
else r.len=1;//r為0的情況
r.i=x.i+y.i;
return r;
}
void BIGINT::print()
{
int j,k;
for(j=this->len-1;j>=this->i;j--)//輸出了len-i個或是一個也還沒輸出
printf("%d",this->data[j]);
if(j==-1){
putchar('\n');
return;}
putchar('.');
if(j<this->i)//小數點后要補零
for(k=this->i-1;k>j;k--)
putchar('0');
for(;j>=0;j--)
printf("%d",this->data[j]);
putchar('\n');
}
BIGINT cToBigint(char c[])
{
int clen=(int)strlen(c),i=0,j=clen-1,k;
BIGINT result;
memset(result.data,0,sizeof(result.data));
while(c[i]=='0'&&i<clen-1)i++;
while(c[j]=='0'&&j>=0)j--;
if(j>i){
result.len=j-i;
for(j=result.len-1;c[i]!='.';j--,i++)
result.data[j]=c[i]-'0';
result.i=j+1;
for(i++;j>=0;j--,i++)
result.data[j]=c[i]-'0';}
else if(j<i){//
result.len=1;
result.i=0;}
else if(i==j&&c[i]!='.'){//完全就是整數,沒有小數點
for(j=clen-1,k=0;j>=i;j--,k++)
result.data[k]=c[j]-'0';
result.len=k;
result.i=0;
}
return result;
}
int main()
{
BIGINT R,result;
int n,i;
char c[Max_b];
while(scanf("%s %d",c,&n)!=EOF){
memset(result.data,0,sizeof(result.data));
result.i=0;
result.len=1;
R=cToBigint(c);
result.data[0]=1;
for(i=1;i<=n;i++)
result=result*R;
result.print();
}
return 0;
}
| |||||||||
| 日 | 一 | 二 | 三 | 四 | 五 | 六 | |||
|---|---|---|---|---|---|---|---|---|---|
| 26 | 27 | 28 | 29 | 30 | 31 | 1 | |||
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | |||
| 9 | 10 | 11 | 12 | 13 | 14 | 15 | |||
| 16 | 17 | 18 | 19 | 20 | 21 | 22 | |||
| 23 | 24 | 25 | 26 | 27 | 28 | 29 | |||
| 30 | 1 | 2 | 3 | 4 | 5 | 6 | |||
