poao899 968K 265MS G++ 0.78K 2009-10-31 14:47:43 .
正在認真考慮不要依照OJ分類而依照題目來源分類
queue.
應該跟TIOJ 1501頗像不過不懂1501WA在哪裡
是說他沒要我輸出長度我竟然把長度輸出了QQ
敗尺(?
噢是USACO1.3 Calf Flac懶得co先回來TIOJ
//********************************
#include<stdio.h>
int len,mlen,front,rear,l,r;
char in[1000001];
int used[26];
main(){
while(scanf("%d",&len),len){
getchar();
gets(in);
for(int i=0;i<26;i++)used[i]=0;
rear=0;
for(int cnt=0;cnt<26&&rear<len;rear++){
if(used[in[rear]-'a']==0)cnt++;
used[in[rear]-'a']++;
}
mlen=rear;
l=0;
r=rear-1;
if(rear==len){puts("not found");continue;}
for(front=0;rear<len;rear++){
used[in[rear]-'a']++;
for(;used[in[front]-'a']>1;front++)
used[in[front]-'a']--;
if(rear-front+1<mlen){
mlen=rear-front+1;
l=front;
r=rear;
}
}
for(int i=l;i<=r;i++)
putchar(in[i]);
puts("");
}
}
2009年10月30日 星期五
zj d503 第四題：在凸多邊型內或外
poao899 d503. 第四題：在凸多邊型內或外 AC (4ms, 688KB) 2009-10-30 19:23 .
第一題計算幾何>//<
本來是想找寵物雞(離散greedy?)測資範圍翻到的
是說本來以為不會碰zj了結果還是XD
//************************************
#include<stdio.h>
int getint(){
int g=0,s=1,c=getchar();
while(c==10||c==32||c==9||c==',')c=getchar();
if(c=='-')s=-1,c=getchar();
while(c>='0'&&c<='9'){
g=g*10+c-48;
c=getchar();
}
return g*s;
}
struct point{
int x,y;
void get(){
x=getint();
y=getint();
}
}P[50],test;
int cross(point *o,point *p,point *q){
long long t=((long long)q->x - (long long)o->x)*((long long)p->y - (long long)o->y) - ((long long)q->y - o->y)*((long long)p->x - o->x);
return t==0?0:t>0?1:-1;
}
int n,dir;
main(){
while(~scanf("%d",&n)){
for(int i=0;i<n;i++)
P[i].get();
test.get();
dir=cross(P,P+1,&test);
int i;
for(i=1;i<n;i++){
int c=cross(P+i-1,P+i,&test);
if(c==0){
puts("IN");
break;
}
if(dir*c<0){
puts("OUT");
break;
}
}
if(i==n)puts("IN");
}
}
第一題計算幾何>//<
本來是想找寵物雞(離散greedy?)測資範圍翻到的
是說本來以為不會碰zj了結果還是XD
//************************************
#include<stdio.h>
int getint(){
int g=0,s=1,c=getchar();
while(c==10||c==32||c==9||c==',')c=getchar();
if(c=='-')s=-1,c=getchar();
while(c>='0'&&c<='9'){
g=g*10+c-48;
c=getchar();
}
return g*s;
}
struct point{
int x,y;
void get(){
x=getint();
y=getint();
}
}P[50],test;
int cross(point *o,point *p,point *q){
long long t=((long long)q->x - (long long)o->x)*((long long)p->y - (long long)o->y) - ((long long)q->y - o->y)*((long long)p->x - o->x);
return t==0?0:t>0?1:-1;
}
int n,dir;
main(){
while(~scanf("%d",&n)){
for(int i=0;i<n;i++)
P[i].get();
test.get();
dir=cross(P,P+1,&test);
int i;
for(i=1;i<n;i++){
int c=cross(P+i-1,P+i,&test);
if(c==0){
puts("IN");
break;
}
if(dir*c<0){
puts("OUT");
break;
}
}
if(i==n)puts("IN");
}
}
2009年10月26日 星期一
TIOJ 1385 芳佳的打工
poao899 3944K 120MS G++ 0.37K 2009-10-26 22:29:48 .
唔記憶體差蝴蝶一點點Q
編輯距離。
詳見wiki：編輯距離(English)
是說一開始那個初始化炸掉超不甘心的
還沒找到反例(?
//**********************************
#include<stdio.h>
int dp[1001][1001],i,j;
char a[1001],b[1001];
main(){
gets(a+1);
gets(b+1);
for(i=1;a[i];i++)
dp[i][0]=i;
for(j=1;b[j];j++)
dp[0][j]=j;
for(i=1;a[i];i++)
for(j=1;b[j];j++){
dp[i][j]=(dp[i-1][j]<?dp[i][j-1])+1;
dp[i][j]<?=(dp[i-1][j-1]+(a[i]!=b[j]));
//printf("%d %d:%d\n",i,j,dp[i][j]);
}
printf("%d\n",dp[i-1][j-1]);
}
延伸：
1.滾動?
2.找出如果
for(i=1;i<1001;i++)
dp[i][0]=i;
for(j=1;j<1001;j++)
dp[0][j]=j;
反例
反例
唔記憶體差蝴蝶一點點Q
編輯距離。
詳見wiki：編輯距離(English)
是說一開始那個初始化炸掉超不甘心的
還沒找到反例(?
//**********************************
#include<stdio.h>
int dp[1001][1001],i,j;
char a[1001],b[1001];
main(){
gets(a+1);
gets(b+1);
for(i=1;a[i];i++)
dp[i][0]=i;
for(j=1;b[j];j++)
dp[0][j]=j;
for(i=1;a[i];i++)
for(j=1;b[j];j++){
dp[i][j]=(dp[i-1][j]<?dp[i][j-1])+1;
dp[i][j]<?=(dp[i-1][j-1]+(a[i]!=b[j]));
//printf("%d %d:%d\n",i,j,dp[i][j]);
}
printf("%d\n",dp[i-1][j-1]);
}
延伸：
1.滾動?
2.找出如果
for(i=1;i<1001;i++)
dp[i][0]=i;
for(j=1;j<1001;j++)
dp[0][j]=j;
反例
反例
2009年10月24日 星期六
TIOJ 1411 Ragnarök
poao899 7816K 452MS G++ 0.71K 2009-10-23 12:44:52 .
算是DP....吧
想了頗久其實
好像從一兩個月前就在注意這題了
n=10^6所以不O(n)不容易過(?
想了好多奇怪性質
例如說本來以為每個左界的右界有單調性
但是被＋＋－－＋＋＋－打敗了
不過很多人都寫出記憶體超小的超詭異QQ
//*********************************
#include<stdio.h>
#define MAX 1000000
int DP[MAX*2+1],n,sum,max;
int getint(){
int g=0,c=getchar();
while(c==10||c==9||c==32)c=getchar();
if(c==EOF)return -1;
while(c>='0'&&c<='9'){
g=g*10+c-48;
c=getchar();
}
return g;
}
int get(){
char c=getchar();int a=1;
while(c==10||c==32||c==9)c=getchar();
if(c=='-')a=-1;
if(c=='0')a=0;
while(c!=10)c=getchar();
return a;
}
main(){
int *dp=DP;
while(~(n=getint())){
for(int i=-n;i<=n;i++)
dp[i+MAX]=-1;
sum=max=0;
dp[MAX]=0;
for(int i=0;i<n;i++){
sum+=get();
//printf("%d %d max%d dp[sum+MAX]%d\n",sum,i,max,dp[sum+MAX]);
dp[sum+MAX]==-1?dp[sum+MAX]=i+1:max>?=i-dp[sum+MAX]+1;
}
printf("%d\n",max);
}
}
算是DP....吧
想了頗久其實
好像從一兩個月前就在注意這題了
n=10^6所以不O(n)不容易過(?
想了好多奇怪性質
例如說本來以為每個左界的右界有單調性
但是被＋＋－－＋＋＋－打敗了
不過很多人都寫出記憶體超小的超詭異QQ
//*********************************
#include<stdio.h>
#define MAX 1000000
int DP[MAX*2+1],n,sum,max;
int getint(){
int g=0,c=getchar();
while(c==10||c==9||c==32)c=getchar();
if(c==EOF)return -1;
while(c>='0'&&c<='9'){
g=g*10+c-48;
c=getchar();
}
return g;
}
int get(){
char c=getchar();int a=1;
while(c==10||c==32||c==9)c=getchar();
if(c=='-')a=-1;
if(c=='0')a=0;
while(c!=10)c=getchar();
return a;
}
main(){
int *dp=DP;
while(~(n=getint())){
for(int i=-n;i<=n;i++)
dp[i+MAX]=-1;
sum=max=0;
dp[MAX]=0;
for(int i=0;i<n;i++){
sum+=get();
//printf("%d %d max%d dp[sum+MAX]%d\n",sum,i,max,dp[sum+MAX]);
dp[sum+MAX]==-1?dp[sum+MAX]=i+1:max>?=i-dp[sum+MAX]+1;
}
printf("%d\n",max);
}
}
2009年10月22日 星期四
TIOJ 1361 零的法則
poao899 -8K 750MS G++ 0.42K 2009-10-22 21:18:22 .
唔只要TIOJ 1021 G.Counting Page Numbers過了這題就可以寫了ˊˇˋ
//*********************************************
#include<stdio.h>
unsigned __int64 count(int n){
unsigned __int64 cnt=0;
if(n==-1)return -1;
for(unsigned __int64 i=1;i*10<=n;i*=10){
int m=n/i/10;
cnt+=(m-1)*(i);
if((n/i)%10)
cnt+=i;
else
cnt+=n%i+1;
}
return cnt;
}
main(){
int a,b;
while(~scanf("%d%d",&a,&b)){
if(a>b){int c=a;a=b;b=c;}
//printf("%I64d %I64d\n",count(b),count(a));
printf("%I64u\n",count(b)-count(a-1));
}
}
唔只要TIOJ 1021 G.Counting Page Numbers過了這題就可以寫了ˊˇˋ
//*********************************************
#include<stdio.h>
unsigned __int64 count(int n){
unsigned __int64 cnt=0;
if(n==-1)return -1;
for(unsigned __int64 i=1;i*10<=n;i*=10){
int m=n/i/10;
cnt+=(m-1)*(i);
if((n/i)%10)
cnt+=i;
else
cnt+=n%i+1;
}
return cnt;
}
main(){
int a,b;
while(~scanf("%d%d",&a,&b)){
if(a>b){int c=a;a=b;b=c;}
//printf("%I64d %I64d\n",count(b),count(a));
printf("%I64u\n",count(b)-count(a-1));
}
}
2009年10月21日 星期三
TIOJ 1127 鋪磁磚問題
poao899 -8K 15MS G++ 0.21K 2009-10-22 12:16:51 .
唔花了一節國文課導DP式
本來想用巧拼來寫(?
//*******************************
#include<stdio.h>
int i;
long long dp1[21],dp2[21];
main(){
for(i=*dp1=*dp2=1;i<21;i++){
dp2[i]=dp1[i-1]*2+dp2[i-1];
dp1[i]=dp2[i]+dp1[i-1];
}
while(~scanf("%d",&i))
printf("%I64d\n",dp1[i/2]);
}
唔花了一節國文課導DP式
本來想用巧拼來寫(?
//*******************************
#include<stdio.h>
int i;
long long dp1[21],dp2[21];
main(){
for(i=*dp1=*dp2=1;i<21;i++){
dp2[i]=dp1[i-1]*2+dp2[i-1];
dp1[i]=dp2[i]+dp1[i-1];
}
while(~scanf("%d",&i))
printf("%I64d\n",dp1[i/2]);
}
TIOJ 1103 F.假日的奇想曲
nolonger 108K 781MS G++ 0.24K 2009-10-21 19:59:58 .
唔好陰險這題
"如果答案超過10000，只要輸出最後四位數就好。"
"最後四位"orz
謝謝書泓(?
//************************************
#include
int dp[20010];
int way[10001];
int n;
main(){
dp[0]=1;
for(int i=1;i<=10000;way[i]=dp[2*i],i++)
for(int j=1;j<=i*2;j++)
dp[j]=(dp[j]+dp[j-1])%10000;
while(scanf("%d",&n),n)
printf(n>7?"%04d\n":"%d\n",way[n]);
}
唔好陰險這題
"如果答案超過10000，只要輸出最後四位數就好。"
"最後四位"orz
謝謝書泓(?
//************************************
#include
int dp[20010];
int way[10001];
int n;
main(){
dp[0]=1;
for(int i=1;i<=10000;way[i]=dp[2*i],i++)
for(int j=1;j<=i*2;j++)
dp[j]=(dp[j]+dp[j-1])%10000;
while(scanf("%d",&n),n)
printf(n>7?"%04d\n":"%d\n",way[n]);
}
2009年10月19日 星期一
TIOJ 1452 巧拼放置問題
poao899 460K 228MS G++ 0.77K 2009-10-19 22:28:45 .
耶總算過了XD
O( n*4^m)超噁心複雜度orz
總狀態數O(n*2^m) 狀態轉移O(2^m)
不知道當時考出來puts("0")騙分可以騙幾筆XD
耶今天練習賽被電爆不開心XD
//***********************************
#include<stdio.h>
long long way[13][8192];int n,m;
long long dp(int stat,int nstat,int nown,int nowm){
if(nown>=n)return stat==0;
if(nowm==0 && way[nown][stat])return way[nown][stat];
if(nowm>=m)return dp(nstat,0,nown+1,0);
long long ways=0;
if((stat & (1<<nowm)) ==0){
ways+=dp(stat|(1<<nowm) , nstat|(1<<nowm) , nown , nowm+1);
if(nowm<m-1 && (stat & (1<<nowm+1)) ==0){
ways+=dp(stat|(1<<nowm+1)|(1<<nowm) , nstat , nown , nowm+2);
}
}
else{
ways+=dp(stat,nstat,nown,nowm+1);
}
if(nowm==0)way[nown][stat]=ways;
return ways;
}
main(){
while(scanf("%d%d",&n,&m),n+m){
for(int i=0;i<12;i++)
for(int j=0;j<4096;j++)
way[i][j]=0;
if(n%2 && m%2){puts("0");continue;}
if(n<m){int t=m;m=n;n=t;}
printf("%I64d\n",dp(0,0,0,0));
}
}
2009年10月18日 星期日
UVa 357 Let Me Count The Ways
357 Let Me Count The Ways Accepted C++ 0.012 2009-10-18 07:31:20 .
唔破了一次AC QQ
有注意到是long long但是沒有處理0
然後忘了改%lld 好幾次WA
還有一個不小心刪了一個空白吃了UVa第一個PE
//***********************************
#include <stdio.h>
long long dp[30500];
int coin[5]={1,5,10,25,50},n;
main(){
for(int i=0;i<5;i++){
dp[coin[i]]++;
for(int j=0;j<30010;j++)
dp[j+coin[i]]+=dp[j];
}
while(~scanf("%d",&n))
dp[n]>1?printf("There are %lld ways to produce %d cents change.\n",dp[n],n):printf("There is only 1 way to produce %d cents change.\n",n);
}
唔破了一次AC QQ
有注意到是long long但是沒有處理0
然後忘了改%lld 好幾次WA
還有一個不小心刪了一個空白吃了UVa第一個PE
//***********************************
#include <stdio.h>
long long dp[30500];
int coin[5]={1,5,10,25,50},n;
main(){
for(int i=0;i<5;i++){
dp[coin[i]]++;
for(int j=0;j<30010;j++)
dp[j+coin[i]]+=dp[j];
}
while(~scanf("%d",&n))
dp[n]>1?printf("There are %lld ways to produce %d cents change.\n",dp[n],n):printf("There is only 1 way to produce %d cents change.\n",n);
}
UVa 10684 The jackpot
10684 The jackpot Accepted C++ 0.096 2009-10-18 07:00:02 .
最大連續和
謝謝書泓>////<
原來不用開全部陣列存ˊˇˋ
是說中間那裡有點醜QQ
一次AC.
//***********************************
#include <stdio.h>
int t,n,sum,max;
main(){
while(~scanf("%d",&t),t){
sum=max=0;
for(int i=0;i<t;i++){
scanf("%d",&n);
sum=sum>0?n>0?sum+n:sum+n>?0:n>0?n:0;
max>?=sum;
}
max?printf("The maximum winning streak is %d.\n",max):puts("Losing streak.");
}
}
最大連續和
謝謝書泓>////<
原來不用開全部陣列存ˊˇˋ
是說中間那裡有點醜QQ
一次AC.
//***********************************
#include <stdio.h>
int t,n,sum,max;
main(){
while(~scanf("%d",&t),t){
sum=max=0;
for(int i=0;i<t;i++){
scanf("%d",&n);
sum=sum>0?n>0?sum+n:sum+n>?0:n>0?n:0;
max>?=sum;
}
max?printf("The maximum winning streak is %d.\n",max):puts("Losing streak.");
}
}
2009年10月17日 星期六
UVa 10192 Vacation
10192 Vacation Accepted C++ 0.008 2009-10-18 06:38:50 .
又用火狐連不上UVa了
得動用Google Chromeˊˋ
LCS...幸好一次co對XD
唔詞窮了
//******************************************
#include<stdio.h>
#include<string.h>
int lcs[150][150],cnt=0;
char a[150],b[150];
main(){
a[0]=b[0]='#';
while(gets(a+1)){
cnt++;
if(a[1]=='#')return 0;
gets(b+1);
int la=strlen(a),lb=strlen(b);
for(int i=1;i<la;i++){
for(int j=1;j<lb;j++){
if(a[i]==b[j])
lcs[i][j]=(lcs[i-1][j]>?lcs[i][j-1]>?lcs[i-1][j-1]+1);
else
lcs[i][j]=lcs[i-1][j]>?lcs[i][j-1];
}
}
printf("Case #%d: you can visit at most %d cities.\n",cnt,lcs[la-1][lb-1]);
}
}
又用火狐連不上UVa了
得動用Google Chromeˊˋ
LCS...幸好一次co對XD
唔詞窮了
//******************************************
#include<stdio.h>
#include<string.h>
int lcs[150][150],cnt=0;
char a[150],b[150];
main(){
a[0]=b[0]='#';
while(gets(a+1)){
cnt++;
if(a[1]=='#')return 0;
gets(b+1);
int la=strlen(a),lb=strlen(b);
for(int i=1;i<la;i++){
for(int j=1;j<lb;j++){
if(a[i]==b[j])
lcs[i][j]=(lcs[i-1][j]>?lcs[i][j-1]>?lcs[i-1][j-1]+1);
else
lcs[i][j]=lcs[i-1][j]>?lcs[i][j-1];
}
}
printf("Case #%d: you can visit at most %d cities.\n",cnt,lcs[la-1][lb-1]);
}
}
TIOJ 1021 G.Counting Page Numbers
poao899 -8K 15MS G++ 0.53K 2009-10-17 23:53:38 .
數學(死
感謝書泓雖然他看不到XD
是說0實在太煩了orz他的處理好討厭QQ
//***********************************
#include<stdio.h>
main(){
int k,n;
__int64 cnt,i;
while(~scanf("%d%d",&n,&k)){
cnt=0;
if(k){
for(i=1;i<=n;i*=10){
int m=n/i;
cnt+=m/10*i;
if(k<m%10)cnt+=i;
else if(k==m%10)cnt+=n%i+1;
}
}
else{
for(i=1;i*10<=n;i*=10){
int m=n/i/10;
cnt+=(m-1)*(i);
if((n/i)%10)
cnt+=i;
else
cnt+=n%i+1;
}
}
printf("%I64d\n",cnt);
}
}
數學(死
感謝書泓雖然他看不到XD
是說0實在太煩了orz他的處理好討厭QQ
//***********************************
#include<stdio.h>
main(){
int k,n;
__int64 cnt,i;
while(~scanf("%d%d",&n,&k)){
cnt=0;
if(k){
for(i=1;i<=n;i*=10){
int m=n/i;
cnt+=m/10*i;
if(k<m%10)cnt+=i;
else if(k==m%10)cnt+=n%i+1;
}
}
else{
for(i=1;i*10<=n;i*=10){
int m=n/i/10;
cnt+=(m-1)*(i);
if((n/i)%10)
cnt+=i;
else
cnt+=n%i+1;
}
}
printf("%I64d\n",cnt);
}
}
TIOJ 1505 Assssss!! (短碼)
poao899 384K 531MS G++ 0.50K 2009-02-09 14:20:00 .
其實很久以前就寫過這題了XD
不過今天突然靈機一動寫了短碼
看到shik學長的2296MS還猶豫了一下為什麼跑這麼久
皮皮學長的515是已經用了不快的std::__gcd()
原來是cin<< 囧
不過皮皮學長不用cin<<就0.13K(抖
知道cin以後就不難壓到0.13Kˇ
#import<algo.h>
int n,a,b;
main(){
for(cin>>a;cin>>n>>b>>a;puts(a-1?"zzz...":"Asssss!!"))
for(;n-->2;a/=std::__gcd(a,b))cin>>b;
}
其實很久以前就寫過這題了XD
不過今天突然靈機一動寫了短碼
看到shik學長的2296MS還猶豫了一下為什麼跑這麼久
皮皮學長的515是已經用了不快的std::__gcd()
原來是cin<< 囧
不過皮皮學長不用cin<<就0.13K(抖
| 1 | 59294 | nolonger | 144K | 2296MS | G++ | 0.12K | 2009-10-17 17:14:16 |
| 2 | 48810 | shik | 140K | 2296MS | G++ | 0.12K | 2009-03-08 14:29:41 |
| 3 | 59289 | nolonger | 144K | 2312MS | G++ | 0.13K | 2009-10-17 12:41:23 |
| 4 | 59287 | nolonger | 140K | 2312MS | G++ | 0.13K | 2009-10-17 12:39:34 |
| 5 | 45350 | peter50216 | 136K | 515MS | G++ | 0.13K | 2009-02-10 09:31:07 |
知道cin以後就不難壓到0.13Kˇ
#import<algo.h>
int n,a,b;
main(){
for(cin>>a;cin>>n>>b>>a;puts(a-1?"zzz...":"Asssss!!"))
for(;n-->2;a/=std::__gcd(a,b))cin>>b;
}
2009年10月12日 星期一
TIOJ 1135 2.止不住的迴圈
poao899 -4K 15MS G++ 0.84K 2009-10-13 00:13:42 .
這題目(對我而言)好凶狠= =
在此跟TIOJ說聲抱歉吃了我那麼多爛code
整數線性組合的題目。
簡單紀錄一下解法好了XD
以下雷很大不喜者勿入
輸入有四個數字 a,b,c,k
依題目意思可以知道是找出
a + nc = m(2^k) + b
其中n為正整數,m為整數
整理一下會發現
nc + m(2^k) = b - a
即是做出c跟2^k的線性組合 湊成b-a
然後幾個要點
0. c有可能是0= = 就是這點讓我RE好幾遍QQ
1. 如果 gcd(c,2^k) 不是(b-a)的因數 直接輸出FOREVER
2.線性組合做出來是
pc + q(2^k) = gcd(c,2^k)
兩邊同乘就可以得到(b-a)的線性組合
不過要注意
I. n<0
II. n並非合理之最小 正 整數
大概就這樣了XD
以下code 一堆冗贅東西很礙眼
//********************************************
#include<stdio.h>
long long p,q,n;
long long gcd(long long a,long long b){
static int x=0;
if(a%b==0){
p=0;q=1;
return b;
}
long long c,g;
long long tp,tq;
c=a%b;
g=gcd(b,c);
n=a/b;
tp=p;tq=q;
p=tq;
q=tp-n*tq;
return g;
}
//(pow[k]-1)p+cq=gcd()
int a,b,c,k,t;
long long an,bn;
long long pow[64];
main(){
pow[0]=1;
for(int i=1;i<60;i++)
pow[i]=pow[i-1]*2;
scanf("%d",&t);
while(t--){
scanf("%d%d%d%d",&a,&b,&c,&k);
if(c==0){
a==b?puts("0"):puts("FOREVER");
continue;
}
long long g=gcd(pow[k],c);
if(b==a){
puts("0");
continue;
}
if((long long)(b-a)%g!=0){
puts("FOREVER");
continue;
}
an=c/g;
bn=(pow[k])/g;
long long rp=p*((b-a)/g),rq=q*((b-a)/g);
if(rq<0){
rq+=((-rq)-1+bn)/bn*bn;
}
rq-=rq/bn*bn;
printf("%I64d\n",rq);
}
}
這題目(對我而言)好凶狠= =
在此跟TIOJ說聲抱歉吃了我那麼多爛code
| 58880 | poao899 | 1135 | Accepted | -4K | 15MS | G++ | 0.84K | 2009-10-13 00:13:42 |
| 58879 | __ | 1135 | Accepted | -4K | 15MS | G++ | 1.17K | 2009-10-13 00:12:59 |
| 58878 | __ | 1135 | Runtime Error | G++ | 1.1K | 2009-10-13 00:07:52 | ||
| 58877 | __ | 1135 | Runtime Error | G++ | 1.08K | 2009-10-13 00:06:26 | ||
| 58874 | __ | 1135 | Runtime Error | G++ | 1.07K | 2009-10-12 23:53:43 | ||
| 58873 | __ | 1135 | Runtime Error | G++ | 1.05K | 2009-10-12 23:52:55 | ||
| 58872 | __ | 1135 | Runtime Error | G++ | 1.05K | 2009-10-12 23:52:37 | ||
| 58870 | __ | 1135 | Output Limit Exceed | G++ | 1.0K | 2009-10-12 23:50:44 | ||
| 58869 | __ | 1135 | Output Limit Exceed | G++ | 1.0K | 2009-10-12 23:50:26 | ||
| 58868 | __ | 1135 | Output Limit Exceed | G++ | 1.03K | 2009-10-12 23:50:03 | ||
| 58867 | __ | 1135 | Runtime Error | G++ | 1.0K | 2009-10-12 23:49:28 | ||
| 58865 | __ | 1135 | Runtime Error | G++ | 1.0K | 2009-10-12 23:49:07 | ||
| 58864 | __ | 1135 | Runtime Error | G++ | 0.96K | 2009-10-12 23:48:34 | ||
| 58863 | __ | 1135 | Runtime Error | G++ | 0.98K | 2009-10-12 23:48:19 | ||
| 58862 | __ | 1135 | Runtime Error | G++ | 1.0K | 2009-10-12 23:47:57 | ||
| 58861 | poao899 | 1135 | Runtime Error | G++ | 1.01K | 2009-10-12 23:47:32 | ||
| 58860 | poao899 | 1135 | Runtime Error | G++ | 1.01K | 2009-10-12 23:46:39 | ||
| 58859 | poao899 | 1135 | Runtime Error | G++ | 1.01K | 2009-10-12 23:46:16 | ||
| 58856 | poao899 | 1135 | Runtime Error | G++ | 0.96K | 2009-10-12 23:40:05 |
整數線性組合的題目。
簡單紀錄一下解法好了XD
以下雷很大不喜者勿入
輸入有四個數字 a,b,c,k
依題目意思可以知道是找出
a + nc = m(2^k) + b
其中n為正整數,m為整數
整理一下會發現
nc + m(2^k) = b - a
即是做出c跟2^k的線性組合 湊成b-a
然後幾個要點
0. c有可能是0= = 就是這點讓我RE好幾遍QQ
1. 如果 gcd(c,2^k) 不是(b-a)的因數 直接輸出FOREVER
2.線性組合做出來是
pc + q(2^k) = gcd(c,2^k)
兩邊同乘就可以得到(b-a)的線性組合
不過要注意
I. n<0
II. n並非合理之最小 正 整數
大概就這樣了XD
以下code 一堆冗贅東西很礙眼
//********************************************
#include<stdio.h>
long long p,q,n;
long long gcd(long long a,long long b){
static int x=0;
if(a%b==0){
p=0;q=1;
return b;
}
long long c,g;
long long tp,tq;
c=a%b;
g=gcd(b,c);
n=a/b;
tp=p;tq=q;
p=tq;
q=tp-n*tq;
return g;
}
//(pow[k]-1)p+cq=gcd()
int a,b,c,k,t;
long long an,bn;
long long pow[64];
main(){
pow[0]=1;
for(int i=1;i<60;i++)
pow[i]=pow[i-1]*2;
scanf("%d",&t);
while(t--){
scanf("%d%d%d%d",&a,&b,&c,&k);
if(c==0){
a==b?puts("0"):puts("FOREVER");
continue;
}
long long g=gcd(pow[k],c);
if(b==a){
puts("0");
continue;
}
if((long long)(b-a)%g!=0){
puts("FOREVER");
continue;
}
an=c/g;
bn=(pow[k])/g;
long long rp=p*((b-a)/g),rq=q*((b-a)/g);
if(rq<0){
rq+=((-rq)-1+bn)/bn*bn;
}
rq-=rq/bn*bn;
printf("%I64d\n",rq);
}
}
TIOJ 1392 傳訊兵問題extreme
poao899 296K 2046MS G++ 1.22K 2009-10-12 19:49:34 .
唔這題跟1391完全沒關係XD
只是單純的最短路問題XD
我寫spfa速度有變快了好開心XD大概是這題不用建圖吧(咦
不過離開queue忘了處理讓我炸了一次orz
//****************************************************
#include<stdio.h>
#define INF 2147483647
#define qlen 50000
int node[100][100];
int dis[100][100];
int q[qlen][2];
int inq[100][100];
int n,max,front,rear;
int dir[4][2]={{-1,-1},{-1,0},{1,0},{1,1}};
int getint(){
int g=0;char c=getchar();
while(c==32||c==10||c==9)c=getchar();
if(c==EOF)return 0;
while(c>='0'&&c<='9'){
g=g*10+c-48;
c=getchar();
}
return g;
}
main(){
while(n=getint()){
max=0;
front=0;
rear=1;
for(int i=0;i<n;i++)
for(int j=0;j<=i;j++){
node[i][j]=getint();
dis[i][j]=INF;
inq[i][j]=0;
}
dis[0][0]=node[0][0];
q[0][0]=q[0][1]=0;
inq[0][0]=1;
while(front!=rear){
int x=q[front][0],y=q[front][1],nx,ny;
for(int i=0;i<4;i++){
nx=x+dir[i][0];
ny=y+dir[i][1];
if(ny>nx || nx>=n || nx<0 || ny<0)continue;
if( ((dis[x][y]>?node[nx][ny])+1) < dis[nx][ny]){
dis[nx][ny] = ((dis[x][y]>?node[nx][ny])+1);
if(!inq[nx][ny]){
q[rear][0]=nx;
q[rear][1]=ny;
rear=++rear%qlen;
inq[nx][ny]=1;
}
}
}
inq[x][y]=0;
front=++front%qlen;
}
for(int i=0;i<n;i++)
for(int j=0;j<=i;j++)
max>?=dis[i][j];
printf("%d\n",max);
}
}
唔這題跟1391完全沒關係XD
只是單純的最短路問題XD
我寫spfa速度有變快了好開心XD大概是這題不用建圖吧(咦
不過離開queue忘了處理讓我炸了一次orz
//****************************************************
#include<stdio.h>
#define INF 2147483647
#define qlen 50000
int node[100][100];
int dis[100][100];
int q[qlen][2];
int inq[100][100];
int n,max,front,rear;
int dir[4][2]={{-1,-1},{-1,0},{1,0},{1,1}};
int getint(){
int g=0;char c=getchar();
while(c==32||c==10||c==9)c=getchar();
if(c==EOF)return 0;
while(c>='0'&&c<='9'){
g=g*10+c-48;
c=getchar();
}
return g;
}
main(){
while(n=getint()){
max=0;
front=0;
rear=1;
for(int i=0;i<n;i++)
for(int j=0;j<=i;j++){
node[i][j]=getint();
dis[i][j]=INF;
inq[i][j]=0;
}
dis[0][0]=node[0][0];
q[0][0]=q[0][1]=0;
inq[0][0]=1;
while(front!=rear){
int x=q[front][0],y=q[front][1],nx,ny;
for(int i=0;i<4;i++){
nx=x+dir[i][0];
ny=y+dir[i][1];
if(ny>nx || nx>=n || nx<0 || ny<0)continue;
if( ((dis[x][y]>?node[nx][ny])+1) < dis[nx][ny]){
dis[nx][ny] = ((dis[x][y]>?node[nx][ny])+1);
if(!inq[nx][ny]){
q[rear][0]=nx;
q[rear][1]=ny;
rear=++rear%qlen;
inq[nx][ny]=1;
}
}
}
inq[x][y]=0;
front=++front%qlen;
}
for(int i=0;i<n;i++)
for(int j=0;j<=i;j++)
max>?=dis[i][j];
printf("%d\n",max);
}
}
2009年10月10日 星期六
TIOJ 1391 傳訊兵問題
poao899 -8K 1577MS G++ 0.48K 2009-10-11 03:16:03 .
簡單DP卻到現在才AC~"~
一開始搞不懂題目orz
看了討論的講解才明白....
是說還手殘吃了一次WA還有自己測的好幾次WA(汗
一次co對這麼難嗎QQ
//*********************************************
#include<stdio.h>
int a[101],b[101];
int n,max;
main(){
int *now=b,*pre=a,*t;
while(~scanf("%d",&n)){
max=-2147483647;
for(int i=0;i<101;i++)
now[i]=pre[i]=2147483647;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
scanf("%d",&now[j]);
(i==1)?:now[j]=(now[j]>?(pre[j] max>?=now[j];
}
t=now;
now=pre;
pre=t;
}
printf("%d\n",max);
}
}
簡單DP卻到現在才AC~"~
一開始搞不懂題目orz
看了討論的講解才明白....
是說還手殘吃了一次WA還有自己測的好幾次WA(汗
一次co對這麼難嗎QQ
//*********************************************
#include<stdio.h>
int a[101],b[101];
int n,max;
main(){
int *now=b,*pre=a,*t;
while(~scanf("%d",&n)){
max=-2147483647;
for(int i=0;i<101;i++)
now[i]=pre[i]=2147483647;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
scanf("%d",&now[j]);
(i==1)?:now[j]=(now[j]>?(pre[j] max>?=now[j];
}
t=now;
now=pre;
pre=t;
}
printf("%d\n",max);
}
}
TIOJ 1291 N箱M球
poao899 148K 150MS G++ 0.48K 2009-10-10 23:08:04 .
唔我排組渣耶= =+
好數學的DP(點頭
第一次見到不是O(1)輸出的DP(抖
是說知道是O(n)輸出後遞迴式就沒那麼難想了....吧XD
被雷到才寫得出來(倒
//*************************************************
#include<stdio.h>
#define M 1000000
int dp[201][201];
int n,m,total;
main(){
dp[0][0]=1;
for(int i=1;i<201;i++)
for(int j=1;j<201;j++)
dp[i][j]=1;
for(int i=1;i<201;i++)
for(int j=1;j<201;j++){
if(i<=j)dp[i][j]=(dp[i-1][j-1]+dp[i][j-1]*i)%M;
else dp[i][j]=0;
}
while(scanf("%d%d",&n,&m),n+m){
total=0;
for(int i=1;i<=n;i++)
total=(total+dp[i][m])%M;
printf("%d\n",total);
}
}
唔我排組渣耶= =+
好數學的DP(點頭
第一次見到不是O(1)輸出的DP(抖
是說知道是O(n)輸出後遞迴式就沒那麼難想了....吧XD
被雷到才寫得出來(倒
//*************************************************
#include<stdio.h>
#define M 1000000
int dp[201][201];
int n,m,total;
main(){
dp[0][0]=1;
for(int i=1;i<201;i++)
for(int j=1;j<201;j++)
dp[i][j]=1;
for(int i=1;i<201;i++)
for(int j=1;j<201;j++){
if(i<=j)dp[i][j]=(dp[i-1][j-1]+dp[i][j-1]*i)%M;
else dp[i][j]=0;
}
while(scanf("%d%d",&n,&m),n+m){
total=0;
for(int i=1;i<=n;i++)
total=(total+dp[i][m])%M;
printf("%d\n",total);
}
}
2009年10月9日 星期五
TIOJ 1017 C.Node of Sequence
poao899 4876K 203MS G++ 0.73K 2009-10-09 21:15:35 .
這個時候才把他AC掉真的超糟糕的XD
奇怪之前怎麼沒想到orz
應該是腦袋不太靈活了(喂
本來應該瞬秒的題目...
第一二個WA是gn沒有處理負號
OLE是沒有殺掉測試用迴圈orz
//*****************************************************
#include <stdio.h>
int ARR[1000000];
bool BOOL[1000000];
int getint(){
int g=0,s=1;char c=getchar();
while(c==32||c==10||c==9)c=getchar();
if(c=='-')s=-1,c=getchar();
while(c>='0'&&c<='9'){
g=g*10+c-48;
c=getchar();
}
return g*s;
}
main(){
int t=getint(),n,max,min,cnt;
int *arr=ARR;
bool *b=BOOL;
while(t--){
min=2147483647;
max=-2147483648;
cnt=0;
n=getint();
for(int i=0;i<n;i++){
b[i]=1;
arr[i]=getint();
}
for(int i=0;i<n;i++){
if(arr[i]<=max)
b[i]=0;
max>?=arr[i];
}
for(int i=n-1;~i;i--){
if(arr[i]>=min)
b[i]=0;
min<?=arr[i];
}
for(int i=1;i<n-1;i++){
//printf("%d:%d\n",i,b[i]);
if(b[i])cnt++;
}
printf("%d\n",cnt);
}
}
這個時候才把他AC掉真的超糟糕的XD
奇怪之前怎麼沒想到orz
應該是腦袋不太靈活了(喂
本來應該瞬秒的題目...
| 58691 | poao899 | 1017 | Accepted | 4876K | 203MS | G++ | 0.73K | 2009-10-09 21:15:35 |
| 58690 | poao899 | 1017 | Output Limit Exceed | G++ | 0.72K | 2009-10-09 21:12:05 | ||
| 58689 | poao899 | 1017 | Wrong Answer | G++ | 0.69K | 2009-10-09 21:10:44 | ||
| 58688 | poao899 | 1017 | Compile Error | G++ | 0.69K | 2009-10-09 21:08:32 | ||
| 58687 | poao899 | 1017 | Wrong Answer | G++ | 0.69K | 2009-10-09 21:06:53 |
第一二個WA是gn沒有處理負號
OLE是沒有殺掉測試用迴圈orz
//*****************************************************
#include <stdio.h>
int ARR[1000000];
bool BOOL[1000000];
int getint(){
int g=0,s=1;char c=getchar();
while(c==32||c==10||c==9)c=getchar();
if(c=='-')s=-1,c=getchar();
while(c>='0'&&c<='9'){
g=g*10+c-48;
c=getchar();
}
return g*s;
}
main(){
int t=getint(),n,max,min,cnt;
int *arr=ARR;
bool *b=BOOL;
while(t--){
min=2147483647;
max=-2147483648;
cnt=0;
n=getint();
for(int i=0;i<n;i++){
b[i]=1;
arr[i]=getint();
}
for(int i=0;i<n;i++){
if(arr[i]<=max)
b[i]=0;
max>?=arr[i];
}
for(int i=n-1;~i;i--){
if(arr[i]>=min)
b[i]=0;
min<?=arr[i];
}
for(int i=1;i<n-1;i++){
//printf("%d:%d\n",i,b[i]);
if(b[i])cnt++;
}
printf("%d\n",cnt);
}
}
2009年10月8日 星期四
TIOJ 1566 簡單易懂的現代都市
poao899 34672K 4151MS G++ 1.71K 2009-09-24 12:22:20 .
這題寫過一段時間了
不過因為這題太可愛了還是放上來好了XD
deque超神秘
當初聽SKYLY學長講到說是deque O(n)時超驚悚的XD
不過寫得怪醜醜的QQ
而且超邪惡的
這題測資有tab !!
害我gn炸了好幾次QQ
/***********************************************
這題寫過一段時間了
不過因為這題太可愛了還是放上來好了XD
deque超神秘
當初聽SKYLY學長講到說是deque O(n)時超驚悚的XD
不過寫得怪醜醜的QQ
而且超邪惡的
這題測資有tab !!
害我gn炸了好幾次QQ
/***********************************************
#include<stdio.h>
#define MAX 10002000
unsigned n,m,k;
unsigned i,l,r,cnt;
unsigned in[10000000];
bool getint(unsigned *a){
unsigned g=0;char c=getchar();
if(c==EOF)return 0;
while(c==10||c==32||c==9)c=getchar();
while(c>='0'&&c<='9'){
g=g*10+c-'0';
c=getchar();
}
*a=g;
return 0;
}
unsigned out[10000000][2];
struct queue{
unsigned q[MAX];
unsigned front,rear;
void ini(){
front=0;
rear=1;
}
unsigned popf(){
unsigned c=q[front];
front=++front%MAX;
return c;
}
unsigned popr(){
rear=(--rear+MAX)%MAX;
return q[rear];
}
unsigned peekf(){
return q[front];
}
unsigned peekr(){
unsigned x=(rear-1+MAX)%MAX;
return q[x];
}
void pushf(unsigned c){
front=(--front+MAX)%MAX;
q[front]=c;
}
void pushr(unsigned c){
q[rear]=c;
rear=++rear%MAX;
}
}max,min;
void mover(unsigned &r){
if(++r < n){
bool b=0;
while(max.front!=max.rear){
if(max.peekf()>=in[r])
break;
max.popf();
}
max.pushf(in[r]);
while(min.front!=min.rear){
if(min.peekf()<=in[r])
break;
min.popf();
}
min.pushf(in[r]);
}
}
void movel(unsigned &l){
if(l+1 < n){
if(min.peekr()==in[l])
min.popr();
if(max.peekr()==in[l])
max.popr();
l++;
}
}
main(){
getint(&n);getint(&m);getint(&k);
//scanf("%u%u%u",&n,&m,&k);
for(i=0;i<n;i++)
getint(in+i);
//scanf("%u",&in[i]);
max.ini();
min.ini();
max.q[0]=in[0];
min.q[0]=in[0];
for(l=r=0;l<n-1||r<n-1;){
if(max.peekr()-min.peekr() == k){
out[cnt][0]=l;
out[cnt][1]=r;
cnt++;
}
if(l || r-l+1==m)
movel(l);
if(r!=n-1)
mover(r);
}
printf("%d\n",cnt);
for(i=0;i<cnt;i++)
printf("%d %d\n",out[i][0]+1,out[i][1]+1);
}
TIOJ 1014 打地鼠
poao899 868K 136MS G++ 1.03K 2009-10-08 22:59:40 .
我寫過的第二題O(n^2*2^n)DP
是說取絕對值
#define abs(x) ((x)>0?(x):-(x))
一開始竟然寫成
#define abs(x) ((x)>0? :-(x))
結果所有正數都變成1(汗
另外無條件進入讓我掙扎了一下
dp[now][stat]=(dp[now][stat]+t[now]-1)/t[now]*t[now];
從正直DE那題問蚯蚓學會的
反正 code
//*******************************************************
#include<stdio.h>
#define abs(x) ((x)>0?(x):-(x))
int dp[16][65536];
int t[16],n;
int dfs(int now,int stat,int pre){
if(dp[now][stat])return dp[now][stat];
if(stat==(1<<n)-1)
return dp[now][stat]=(now+1>t[now]?(now+t[now])/t[now]*t[now]:t[now]);
dp[now][stat]=2147483647;
for(int i=0;i<n;i++)
if((stat&(1<<i))==0)
dp[now][stat]<?=dfs(i,stat|(1<<i),now)+abs((now-i));
dp[now][stat]=(dp[now][stat]+t[now]-1)/t[now]*t[now];
return dp[now][stat];
}
main(){
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",t+i);
int s=0,min=2147483647;
for(int i=0;i<n;i++)
min<?=dfs(i,s|(1<<i),-1);
printf("%d\n",min);
}
我寫過的第二題O(n^2*2^n)DP
是說取絕對值
#define abs(x) ((x)>0?(x):-(x))
一開始竟然寫成
#define abs(x) ((x)>0? :-(x))
結果所有正數都變成1(汗
另外無條件進入讓我掙扎了一下
dp[now][stat]=(dp[now][stat]+t[now]-1)/t[now]*t[now];
從正直DE那題問蚯蚓學會的
反正 code
//*******************************************************
#include<stdio.h>
#define abs(x) ((x)>0?(x):-(x))
int dp[16][65536];
int t[16],n;
int dfs(int now,int stat,int pre){
if(dp[now][stat])return dp[now][stat];
if(stat==(1<<n)-1)
return dp[now][stat]=(now+1>t[now]?(now+t[now])/t[now]*t[now]:t[now]);
dp[now][stat]=2147483647;
for(int i=0;i<n;i++)
if((stat&(1<<i))==0)
dp[now][stat]<?=dfs(i,stat|(1<<i),now)+abs((now-i));
dp[now][stat]=(dp[now][stat]+t[now]-1)/t[now]*t[now];
return dp[now][stat];
}
main(){
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",t+i);
int s=0,min=2147483647;
for(int i=0;i<n;i++)
min<?=dfs(i,s|(1<<i),-1);
printf("%d\n",min);
}
訂閱：
文章 (Atom)