NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » rscpp 的個人資料 » 顯示文章
 文章

顯示文章

這裡允許您檢視這個會員的所有文章。請注意, 您只能看見您有權限閱讀的文章。

文章 - rscpp

頁: [1] 2 3
1
這是npsc官網上提供的參考解
代碼: [選擇]
// npsc2015-j2e-power 國中決 E. 頗旺愛算樹
#include <iostream>
using namespace std;
typedef long long ll;
 ll cal( ll ta , ll tb )
 {
  if( ta <= 1 || tb == 0 ) return -1;
ll ans = 0;
while( tb >= ta ) ans ++, tb /= ta;
  return ans;
}

int main(void)
{
long long int a,n;
cin >> a >> n;
cout << cal(a,n) << endl;
return 0;
}
/*
2 1000000000000000000
10000000000000008 10000000000000007
0 245773583
1 0
1 1
1 1000000000000000000
0 514
1000000000000000000 999999999999999999
0 1000000000000000000
23948029384902 313376348425861413

----out
59
0
-1
-1
-1
-1
-1
0
-1
1

*/


2
NPSC2015國中組決賽 / npsc2015-國中組決賽 F. 頗汪排球球
« 於: 一月 13, 2016, 08:22:51 pm »
我的想法是,傳統的迴文是首尾各比較是否為 相同的字元
改成 N 列,改成(第1列、第N列)、(第2列、N-1列)…兩兩比較是否為 可匹配的兩列

可匹配的兩列:就是找得到有相同的小寫字母。

代碼: [選擇]
/*
npsc2015-j2f-mul   國中組決賽 F. 頗汪排球球

*/

#include <iostream>
#include <cstring>
using namespace std;

bool match(string s1, string s2)
{
bool used[26];
memset(used,false,sizeof(used));
int i;
for(i=s1.size()-1; i>=0; --i) used[ s1[i]-'a' ] = true;
for(i=s2.size()-1; i>=0; --i)
if( used[ s2[i]-'a' ] ) return true;
return false;
}
int main(void)
{
int i,j,k , n,m,t;

string s[100];

cin >> t;
while( t-- )
{
cin >> n;
for(j=0;j<n;++j) cin >> s[j];
bool yes=true;
for(j=0;j<n/2;++j)
{
if( !match( s[j],s[n-1-j] ) )
{
yes=false;
break;
}
}
if(yes) cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
}
/*
3
1
abccc
3
bdcvg
tmt
paul
4
e
d
d
yee

---- out
Yes
No
Yes
*/


3
我覺得解法應是兩兩字串的 (長度和 - LCS ) 找最小的
例如第1組測資
ATTCCG
4
ATG
CGA
ATTCC
TC
(1) ATTCCG+ATG長度和為9 - 3{LCS(ATTCCG,ATG) = 6
(2) ATTCCG+CGA長度和為9 - 2{LCS(ATTCCG,CGA) = 7
(3) ATTCCG+ATTCC長度和為11 - 5{LCS(ATTCCG,ATTCC) = 6
(4) ATTCCG+TC長度和為8 - 2{LCS(ATTCCG,ATG) = 6

例如第2組測資
TCGAATTGCA
2
AAAAAAAAAAAAAAAA
GGGGGGGGGGGGGGGG
(1) TCGAATTGCA+AAAAAAAAAAAAAAAA長度26 - 3{LCS(TCGAATTGCA,AAAAAAAAAAAAAAAA) = 23
(2) TCGAATTGCA+GGGGGGGGGGGGGGGG長度26 -2{LCS(TCGAATTGCA,GGGGGGGGGGGGGGGG) = 24

字串長度各 5000 ,忘了LCS的時間怎麼算了,只算長度應該沒問題

4
代碼: [選擇]
/*
npsc2015-j2d-circle D.
*/

#include <iostream>
using namespace std;
int main(void)
{
long long int r,x,y,r2,x2,y2 , sum;
cin >> r;
r2 = r*r;
sum = 0;
for(x=r, y=0; y<r; ++y)
{
y2 = y*y;
x2 = x*x;
while( x2+y2>r2)
{
--x;
x2=x*x;
}
// cout << y<< ": +" << x << endl;
sum+=x;
}
cout << sum*4+1 << endl;
return 0;
}
/*
1
10
100
1000000

-----out
5
317
31417
3141592649625

*/



5
NPSC2015國中組決賽 / npsc2015國中組決賽-G.光通訊
« 於: 一月 11, 2016, 09:04:49 pm »
本來第1個想法是將七個.更換為空白以sstream方式讀入一word
每一個word的字串再將三個.更換為空白讀入,想想又覺得麻煩,
後來又想到如下的方式,一個字一個字元的處理,
記錄目前讀到的.及=的個數
代碼: [選擇]
/*
npsc2015-j2g-morse 國中決 G.光通訊
sol-1 every char check
*/

#include <iostream>
#include <sstream>
#include <iomanip>
#include <cstring>
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;
const int MaxN = 1000;
int mos[]={12,2111,2121,211,1,  1121,221,1111,11,1222,  212,1211,22,21,222,   1221,2212,121,111,2,  112,1112,122,2112,2122, 2211};
//A  B    C    D   E    F   G    H   I   J      K   L   M  N   O      P   Q     R  S   T    U   V    W   X   Y     Z
char tbl[81];  // A=1+2*3=4 , B=2+1*3+1*9+1*27=41 , J=1+2*3+2*9+2*27;
int main(void)
{
int i,j,k , n;
int p[]={1,3,9,27};
int v,d,e,f;
string s;
// gen tbl
for(i=0; i<26; ++i)
{
k=mos[i];
f=v=0;
e=1000;
while(k>0)
{
j=k/e;
k%=e;
e/=10;
if(j>0) v+=(j*p[f++]);

}
tbl[v] = char(i+'A');
// cout <<char(i+'A') << v << endl;
}


while(cin >>n)  //cin >> n;
{
cin >> s;
v=d=e=f=0;
for(j=0; j<n; ++j)
{
if( s[j] == '.' )
{
++d;
if(e>0)
{
v+=p[f];
if(e==3) v+=p[f];
e=0;
}

}
else // ==
{
++e;
if(d==0) continue;
if(d==1) ++f;
else
{
cout << tbl[v]; //cout << v << " ";
if(d==7) cout << " ";
v=0;
f=0;
}
d=0;
}
}
// last char
if(d==1) ++f;
v+=p[f];
if(e==3) v+=p[f];
cout << tbl[v]<< endl;  // << v << endl;

}

return 0;
}
/*
69
===.=...=.===.===.=...=.=.=...===.=.===.=.......===.===.=...===.===.=
57
=.===...===.=.=.=...===.=.===.=...===.=.=...=...=.=.===.=
53
===.===.=...=.=.=.=...=.=...=.===.===.===...===.=.===
55
=.===.=.=...===.===...===.=...===.===.===...=.===.===.=
47
===.===.=.===...=.===.=...=.=.=...===...=.=.===
65
=.=.=.===...=.===.===...===.=.=.===...===.=.===.===...===.===.=.=

--------out
NPSC GG
ABCDEF
GHIJK
LMNOP
QRSTU
VWXYZ

*/


6
NPSC2015國中組決賽 / npsc2015國中組決賽-E. 頗旺愛算樹
« 於: 一月 11, 2016, 08:54:47 pm »
不很確定哪些算 -1,若有問題請指正
為什麼不可以是 0^1 = 0
代碼: [選擇]
// npsc2015-j2e-power 國中決 E. 頗旺愛算樹
#include <iostream>
using namespace std;

int main(void)
{
long long int k,n,p;
long long int a,b;
while (cin >> a >> n )
{

if ( n==0 ) cout << -1 << endl;
else if( n==1 ) cout << 0 << endl;
else if( a==1 && n!=1 )  cout << -1 << endl;
else if( a>n )  cout << -1 << endl;
else
{
b=n/a;
p=a;
k=1;
while(p<=b)
{
p*=a;
++k;
}
cout << k << endl;
}

}

return 0;
}
/*
0 0
5 1
1 2
2 2
2 3
2 2147483647
3 2
----out
-1
0
-1
1
1
30
-1
*/


7
NPSC2015國中組決賽 / npsc2015國中組決賽- B.艾迪發禮物
« 於: 一月 10, 2016, 09:10:26 pm »
代碼: [選擇]
/*
npsc2015-j2b-gift 國中決 B. 艾迪發禮物
*/

#include <iostream>

using namespace std;

int main(void)
{
int i,j,k , n,m;

while(cin >>n)
{
long long int p=1;
for(j=0;j<n;++j)
{
cin >> i;
p *= (i-j);
}
cout << p << endl;

}

return 0;
}
/*
3
2 3 3
3
2 2 2
20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
20
20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20

-------out
4
0
1
2432902008176640000


*/



8
NPSC2015國中組決賽 / npsc2015國中組決賽- A.河蟹動物小組
« 於: 一月 10, 2016, 09:00:28 pm »
代碼: [選擇]
/*
npsc2015-j2a-animal 國中決 A.河蟹動物小組
*/

#include <iostream>
#include <sstream>
#include <iomanip>
#include <cstring>
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;
const int MaxN = 1000;
int s[6];
int p[10][2][3] = { {{0,1,2},{3,4,5}}  , {{0,1,3},{2,4,5}}
,{{0,1,4},{2,3,5}}  ,{{0,1,5},{2,3,4}}
,{ {0,2,3},{1,4,5}} , {{0,2,4},{1,3,5} }
,{ {0,2,5},{1,3,4}} , {{0,3,4},{1,2,5} }
,{ {0,3,5},{1,2,4}} , {{0,4,5},{1,2,3}}
};
bool nczar(int k, int w)  // 非獨裁 true
{
int a = s[ p[k][w][0] ];
int b = s[ p[k][w][1] ];
int c = s[ p[k][w][2] ];
// cout << a <<"," << b <<"," << c <<"\n";

if( a >= b+c ) return false;
return true;
}

int main(void)
{
int i,j,k , n,m,t;

// 因為只有 6 個數字 ,將 s[]排序, 最大的數字一邊,另5個數字選2,共10種

cin >>t;
while( t-- )
{
cin >> s[0] >> s[1] >> s[2] >> s[3] >> s[4] >> s[5] ;
sort( s, s+6 , greater<int>() );
bool yes=false;
for(k=0; k<10; ++k)
  if( nczar(k,0) && nczar(k,1) )
  {
yes = true;
break;
  }
if(yes) cout <<"Yes" << endl;
else cout <<"No"<< endl;  
}


return 0;
}
/*
4
3 1 4 1 5 9
1 1 1 1 1 1
1 2 3 4 5 6
7 6 5 4 3 2

-------output
No
Yes
No
Yes

*/



9
NPSC2015國中組初賽 / npsc2015國中組初賽 B.胖胖數
« 於: 十二月 10, 2015, 11:08:09 pm »
這一題的時限?   R-L最大差距是多少?   有測資嗎?
如果R-L<10^4而且時限10秒,我的以下想法也許有點希望
又如果 R-L 真的不會太大,而時間差一點,還可以將L~R的迴圈加快6n+1,6n+5
拋磚 希望能 引玉
代碼: [選擇]
/* npsc2015-j1b 胖胖數
這一題的時限? R-L最大差距是多少?有測資嗎?
如果R-L<10^4而且時限10秒,我的以下想法也許有點希望

我有三個函數
void genp(MaxN) 建一質數表,但MaxN不可能10^18,選個數字吧(就1e6)
    我用篩法建bool c[MaxN],並以vector<int> p存 2~MaxN之間的質數

bool isp(long long int k) 傳回是否為質數{簡稱p}

bool ispp( long long int k) 傳回是否胖胖數{簡稱pp}

    1算pp,我將k改為字串 s{假設有10位數abcdefghij} 分段算出sum=a, sum*10+b ,sum*10+c...
    分別判斷a,ab,abc,abcd...,abcdefghij是否為質數只要有一個非則傳回 false
 例 2339933917  {2:p, 23:p, 233:p, 2339:p, 23399:p, 233993:p,
    2339933:p, 23399339:p, 233993391:非p 則傳回 false}
 又例 293997390 {2:p, 29:p, 293:p, 2939:p, 29399:p, 293997:非p 則傳回 false }
*/
#include <iostream>
#include <cstdio>
#include <sstream>
#include <iomanip>
#include <cstring>
#include <vector>
#include <cmath>
using namespace std;
const int MaxN = int(1e6); //50000; //int(1e7);
vector <int> p;
bool c[MaxN];
void genp(int maxn)
{
   int i,j;
   for(i=0;i<maxn;i+=2) c[i]=false , c[i+1]=true;
   c[1]=true;  c[2]=true;   p.push_back(2);
   for(i=3; i<maxn; i+=2)
   {
if( !c[i] ) continue;
p.push_back(i);
    for(j=i+i; j<maxn; j+=i)
      c[j]=false;
   }
   cout << p.size() << ":" << p[p.size()-1] << endl;
}
bool isp(long long int k)
{
   if(k<MaxN) return c[k];
   int q = int(sqrt(k));
int i,j;
for(i=0; i<p.size() && p[i]<=q; ++i)
   if(k%p[i]==0) return false;
cout << "[" << q <<":"<<p[i]<<"]"<<i <<endl;
   if(q<p[i]) return true;
for(i=p[p.size()-1]+2; i<=q; i+=2)
if(k%i==0) return false;
return true;
}
bool ispp(long long int kk)
{
stringstream ss;
string s;
ss << kk;  ss>>s;
  int i;
  long long int k=int(s[0]-'0');
  if( !isp(k) ) return false;
  for(i=1; i<s.size(); ++i)
  {
//if(s[i]=='0' || s[i]=='2' || s[i]=='4' || s[i]=='5' || s[i]=='6' || s[i]=='8') return false;
k=k*10+int(s[i]-'0');
if( !isp(k) ) return false;
  }
  return true;
}
int main()
{
   int i,j;
   genp(MaxN);
   int T;
   long long int L,R,k;
   cin >> T;
   while(T--)
   {
scanf("%lld %lld", &L, &R);
cout << L <<"," <<R << endl;
     int cnt=0;
     if(L<=2) { cnt=3-L; L=3;  cout <<"1 or 2 cnt:" << cnt <<" ]";}
     if(L%2==0) ++L;
   for(k=L; k<=R; k+=2)
   {
if( ispp(k) ) { printf("%lld ", k); ++cnt;}
  //cout <<fixed<<setprecision(10) << log10(k)<<" "<< k <<":" << isp(k) << endl;
   }
   printf("共 %d\n",cnt);
}
  return 0;
}
/*  ---輸入範例
20
1 11
10 100
100 900
1000 3000
37210 98765
3700 5700
1379 3791
13976 23977
1131111 1171111
1151110 1157110
7133271 7339271
31415926535 31415926535
1319399173131 1319399273131
2345789654328763 2345789654338763
77777771 77797771
979793910 979893910
31415926535 31415926535
31415926535 31415926535
323333 399999
23333 29999
---------------輸出範例
6
13
24
17
8
4
19
17
0
0
0
0
0
0
0
0
0
0
2
5

*/


10
NPSC2015國中組初賽 / NPSC2015國中組初賽 F.頗旺愛數樹
« 於: 十二月 10, 2015, 12:10:13 am »
我的想法是 2,4,8只要判斷最後1,2或3位數可否整除即可
計算 奇數位及偶數位的和可以判斷 11的倍數
全部位數和可判斷3、9的倍數
看最後一位應可以判斷5、10的倍數
而6是2x3
程式碼看有沒有人補了,還沒人補,我就補了
代碼: [選擇]
// NPSC2015-j1f F.頗旺愛數樹div
// 是否可被2,3,4,5,6,8,9,10,11整除?{沒有7}
 
#include <iostream>
using namespace std;
bool isdiv(string s , int k)
{
  bool even;
  int i,sum[2]={0,0};
  int n = s.size();
  for(i=0;i<n;++i) sum[i%2] += int(s[i]-'0');
  int sum3 = (s[n-1]-'0') + (s[n-2]-'0')*10 + (s[n-3]-'0')*100;
  switch ( k )
  {
     case 2: case 4: case 8: return (sum3%k==0);
     case 3: case 9:    return ((sum[0]+sum[1])%k==0);
     case 5:    return (s[n-1]=='5' || s[n-1]=='0' );
     case 10:    return (s[n-1]=='0');
     case 6:     return ( sum3%2==0 && (sum[0]+sum[1])%k==0 );
     case 11:    return (sum[0]==sum[1]|| abs(sum[0]-sum[1])%11==0);
//   break;
   }
}
int main()
{
  string s;
  int t ,k;
  while(cin >>t)
  while(t--)
  {
     cin >> s >> k;
     cout << ( isdiv(s,k) ? "YES" : "NO" ) << endl;
  }
  system("pause");
  return 0;
}
/*
2
514 2
514 3
3
10077696 6
555111444 5
123456654321 11
4
100000000000000000000 5
3112 4
4212 8
3112 8
----------
Yes
No
Yes
No
Yes
Yes
Yes
No
Yes
*/

11
NPSC2015國中組初賽 / NPSC2015國中組初賽 E.小希取名字
« 於: 十二月 09, 2015, 11:57:32 pm »
// 30組、每組一列最長 10萬個字,沒測資不確定是否可行,應該最多 30x25x10^5
//  因為英文字母最多26個,將字串的min(前25字,字串長-1)串接在字串後 即可達到環狀的效果
//  擴增字串從第1字開始,出現的字母記號並記數,直到重複,下一段由被重複的下1字開始
代碼: [選擇]
//  npsc2015-j1e NPSC2015國中組初賽 E.小希取名字
//  因為英文字母最多26個,將字串的min(前25字,字串長-1)串接在字串後 即可達到環狀的效果
//  擴增字串從第1字開始,出現的字母記號並記數,直到重複,下一段由被重複的下1字開始
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MaxN = 100000;
char s[MaxN+50];
int main( )
{

   int t, i,j,k,a,  n,m;
cin >> t;
   for(i=0; i<t; ++i)
   {
scanf("%s",s);
n = strlen(s);
// cout << n <<" : " << s ;
k = min( n-1 , 25 );
for(a=0,j=n; a<k; ++a, ++j) s[j]=s[a];
s[j]= '\0';  m=j;
// cout << " , " << m <<" : " << s << endl;
int ans=0, cnt=0;
int mk[99];
for(k=65;k<=90;++k) mk[k]=-1;
for(j=0; j<m; ++j)
{
if( mk[s[j]]>=0 ) //出現過
{
if(cnt>ans) ans=cnt;
cnt = 0;
j = mk[s[j]];
if(j>=n) break;
for(k=65;k<=90;++k) mk[k]=-1;
}
else
{
mk[s[j]] = j;
++cnt;
}
}  // for j
  if(cnt>ans) ans=cnt;
  cout << ans << endl;
}
   return 0;
}
/*
5
XDDORZQQ
IKKZZZSSH
ABCXYADFGXHJNDEGJK
ABCXYADFGXHJNDEGVK
OPWQHJNLVEGMKABCXYADFGXHJNCXYADFGXCXYADFGX
------------
5
4
11
13
18
*/

12
NPSC2015國中組初賽 / NPSC2015國中組初賽 D.傳紙條是很辛苦的
« 於: 十二月 09, 2015, 10:33:59 pm »
代碼: [選擇]
//  npsc2015-j1d NPSC2015國中組初賽 D.傳紙條是很辛苦的
//  我使用一個表 t[2][26] 一列加密、一列解碼
#include <iostream>
using namespace std;
int main( )
{
   string s;
   int i,j,k,  n;
   char t[2][26];  //enc使用0、dec使用1
   while(cin >> s)
   {
k=(s[0]!='e');
cin >> s;
for(i=0;i<26;++i)
{
t[0][i]=s[i];
t[1][s[i]-'a']=i+'a';
}
cin >> n >> s;
for(j=0; j<n; ++j)
  cout << (s[j]=='_' ? '_' : t[k][s[j]-'a'] );
cout << endl;

}
   return 0;
}
/*
encrypt
rjfzowngxeqkmcihtdyvlbpasu
24
this_is_a_secret_message
decrypt
rjfzowngxeqkmcihtdyvlbpasu
24
vgxy_xy_r_yofdov_moyyrno
decrypt
psivaykmbjgtcouhwdrxzelnfq
52
iuokdpxztpxbuor_mada_br_fuzd_ytpk_ohri_br_ru_plaruca
------------
vgxy_xy_r_yofdov_moyyrno
this_is_a_secret_message
congratulations_here_is_your_flag_npsc_is_so_awesome
*/

13
NPSC2015國中組初賽 / NPSC2015國中組初賽-C.跳躍的波利
« 於: 十二月 09, 2015, 10:04:01 pm »
//  npsc2015-j1c
我使用一個 struct slop {int x, y;}存兩點的斜率,存化成最簡的斜率,若為負統一設定x為負,
若 x位移為0則y設為1或-1 ,若 y位移為0則x設為1或-1,
比較前一個 位移斜率 及接續的 位移斜率是否相等即可
我有三個函數{cmp:比較兩個斜率是否不相等,gcd:最大公因數,getslop(給兩點的x,y位移)算斜率}
代碼: [選擇]
//  npsc2015-j1c
//存化成最簡的斜率,若為負統一設定x為負
//若 x位移為0則y設為1或-1 ,若 y位移為0則x設為1或-1
// 比較前一個 位移斜率 及接續的 位移斜率是否相等即可

#include <iostream>
#include <vector>
using namespace std;
struct slop
{
  int x;
  int y;
};
bool cmp(slop a, slop b)  // != 為 true
{
  return ((a.x != b.x) || (a.y != b.y));
}
int gcd(int a, int b)
{
   int r=a%b;
while(r)
{
  a=b; b=r; r=a%b;
}
return b;
}
slop getslop(int xd, int yd)
{
   slop m; //斜率
if(xd==0)
{
m.x=0;
m.y= (yd<0?-1:1);
return m;
}
if(yd==0)
{
m.y=0;
m.x= (xd<0?-1:1);
return m;
}
bool sgn = (xd*yd<0);   // 斜率為 負
xd=abs(xd); yd=abs(yd);
int g = gcd(xd, yd);
xd /= g; if(sgn) xd*=-1;
yd /= g;
m.x = xd;  m.y=yd;
return m;
}
int main( )
{
   int  n , i , j , k;
   int x[2],y[2], xd,yd;
   slop m[2];
   while(cin >> n)
   {
vector <int> ans;
int cnt=0;
cin >> x[0] >> y[0] >> x[1] >> y[1];
m[0] = getslop( x[1]-x[0] , y[1]-y[0] );  //第0-1點 斜率
//cout << "0-1:" << m[0].y << "/" << m[0].x << endl;
for(i=2,j=0; i<n; ++i,j=1-j)
{
cin >> x[j] >> y[j];
m[1-j] = getslop( x[j]-x[1-j] , y[j]-y[1-j] );
if( cmp(m[0] , m[1]) )
{
  ++cnt;
  ans.push_back(i);
}
//cout << i-1 << "-" << i << ":"  << m[1-j].y << "/" << m[1-j].x << endl;
}
//cout << endl;
cout << cnt << endl;
for(i=0; i<ans.size(); ++i)
  cout << ans[i] << endl;
}
   
   return 0;
}
/*
7
0 0
1 1
2 2
1 2
0 2
1 1
2 0
5
0 0
0 1
1 1
1 0
0 0
------------
2
3
5
3
2
3
4
*/


14
NPSC2015國中組初賽 / npsc2015國中組初賽- A.換換換
« 於: 十二月 09, 2015, 07:14:00 pm »
 n , x , y
 if( n==x) 則在 y
 else  if( n==y) 則在 x
 else 則為 n

15
NPSC2001高中組初賽 / Re: NPSC 2001 高初 A.坦克任務
« 於: 六月 15, 2015, 05:20:44 pm »
當初的想法應該有誤
本來想的比較單純,但要coding時愈看愈有問題,又剛好較忙,就放著
這兩天仔細看了一下,確定不行,但好像不容易哦!

炸掉敵方的炮臺順序不同也有不同的步數,所以新的想法如下

沒炸、炸1個、炸2個、炸3個、炸4個,全排列共65種各跑一次

而每跑一次的部份,找到要炸的砲臺的最短路徑s1+炸完後的最短路徑s2
▲ s2是將可炸掉砲臺的位置當起點來算
▲ 又剛炸完一個砲臺後需更新戰場的狀況(該砲臺位置不可走,其威脅的格子解除該砲的威脅,某些格仍會被其它砲威脅到哦)

程式碼好像要花點時間,但感覺有點方向了。

以上程式是假設戰場大小 1000x1000以內,較大可能就???
又如果戰場很小,例15x15也許可以另一種寫法吧

16
NPSC2001高中組初賽 / NPSC 2001 高初 B.錢幣王國
« 於: 五月 31, 2015, 06:05:01 pm »
因錢幣種類最多2000,即費氏數f(2000)很大,若以大數法好像不大好哦,我的想法如下:

某人的錢幣總價值可轉換為費氏表示式,各個位置的權值如下,每一位只能0或1,且不可能連續1
位置: 1  2  3  4  5  6  7 ...
權值: 1  1  2  3  5  8  13 ...
   若有連續{...,X,1,1,Y,...}可轉成{...,X,0,0,Y+1,...}
   若有>1且第3種錢幣之後{...,X,Y,2,Z,...}可轉成{...,X+1,Y,1,Z+1,...}
   但若是第1或第2種 {X,2,Y,...}=>{X,0,Y+1,...} 或 {2,X,Y,...}=>{0,X,Y+1,...}
假設讀入如下:
(1)讀入 2 1 3 1 5 1 0即 {0,1,1,0,1}但2、3連續所以→{0,0,0,1,1}又4、5連續→最後{0,0,0,0,0,1}
(2)讀入 3 5 0 即{0,0,5}→{2,0,1,2}→{2,1,1,0,1}→{2,0,0,1,1}→{2,0,0,0,0,1}→{0,0,1,0,0,1}
(3)讀1 145 0 即{145}→{1,0,72}→{37,0,0,36}→{37,18,0,0,18}→…{1,0,0,0,0,0,0,0,0,0,0,1}
每組兩個錢幣值轉為費氏表示法後,再由最高位往低位比,即可判斷大小。

我的程式如下
代碼: [選擇]
// npsc01-s1b.cpp  npsc 2001 高初 B 錢幣王國
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstring>
using namespace std;
const int maxn = 2100; //錢幣種類 最多 2000,但數量最多 10000,若進位 應不會超過 20位
int  a[2][maxn] , mm[2];
void t2f(int i)
{
int j , p=mm[i] , d;
int mp = p;
while( p )
{
if(p>mp) mp=p;
if(p>2)
{
if(a[i][p]>=2)
{
d = a[i][p]/2;
a[i][p] %= 2;
a[i][p+1] += d;
a[i][p-2] += d;
p+=1;
}
else if( a[i][p]==1 && (a[i][p+1]==1 || a[i][p-1]==1)  ) // 有可能[p+1]=1 或 [p-1]=1;
{
if(a[i][p+1]==1) ++p;
a[i][p+1] += 1;
--a[i][p];
--a[i][p-1];
p+=1;
}
else --p;
}
else  // p=1,2

d = (a[i][1]<a[i][2] ? a[i][1] : a[i][2]);
if(d)
{  p=3;
a[i][p] += d; a[i][1] -= d; a[i][2] -= d;
} else if(a[i][p]>=2)
{
   d = a[i][p]/2;
   a[i][3] += d;
a[i][p]%=2;
p=3;  
}
else --p;
}
}
mm[i]=mp;   //傳回最高位

// 以下是測試用 多印出的
cout <<"第" << i+1 << "人 ";
for(j=mp; j>0; --j)
  if(a[i][j]) cout << j <<":" <<a[i][j] <<" ";
cout << endl;

}
int cmp()
{
if(mm[0]>mm[1]) return 1;
else if(mm[0]<mm[1]) return -1;
for(int i=mm[0]; i>0; --i)
{
if(a[0][i]>a[1][i]) return 1;
   else if(a[0][i]>a[1][i]) return -1;
}
return 0;
}
int main()
{
  int m;
while( cin >> m )
{
if( m == -1 ) break;
memset(a,0,sizeof(a));
  mm[0] = mm[1] = 0;
   while( cin >> a[0][m]  )
   {
if( m > mm[0] ) mm[0] = m;    
cin >> m;
    if(m==0) break;
}
   t2f(0 );  //將 讀入資料轉成 費氏表示式

   while( cin >> m )
{
if(m==0) break;
cin >> a[1][m];
if( m > mm[1] ) mm[1] = m;    
   }
   t2f(1);
   int r = cmp();
if ( r == 1 ) cout << "MORE" << endl;
else if ( r == -1 ) cout << "LESS" << endl;
else cout << "EVEN" << endl;
}

  return 0;
}
/*
2 1 3 1 5 1 0   
7 1 0
3 5 0   
3 1 6 1 0
1 145 0
12 1 0
10 8 7 6 5 3 9 1 0
9 1 7 6 5 2 3 1 6 2 8 2 10 7 0
-1
--------
第1人 6:1
第2人 7:1
LESS
第1人 6:1 3:1
第2人 6:1 3:1
EVEN
第1人 12:1 1:1
第2人 12:1
MORE
第1人 14:1 12:1 9:1 6:1 4:1 1:1
第2人 14:1 12:1 9:1 6:1 4:1 1:1
EVEN

*/

17
NPSC2001高中組初賽 / NPSC 2001 高初 A.坦克任務
« 於: 五月 31, 2015, 05:24:11 pm »
現在有個想法,但不很確定:
因為敵砲最多只有4個,打掉或不打掉最多 2^4個狀況,各跑一次最短路徑
我預訂將地圖中原空白處的值改為0,而被敵砲威脅到的格子各加該敵砲值{1,2,4,8}
4個皆威脅到的最多+15、都沒威脅到的+0,當設定威脅或取消威脅 ± 該值
若某一格的值非0即不能通過,程式後補吧!

18
NPSC2004國中組決賽 / NPSC 2004 國決 G.交通運輸
« 於: 五月 26, 2015, 10:26:24 pm »
代碼: [選擇]
// npsc04-j2g (NPSC 2004 國中決賽 題目 G 交通運輸)
// (1) 求每個節點 s 至其它節點的距離 d[s][k], k=1~n
// (2) 但 n<=1000 不可以用 n^3的方法,n節點n-1個邊,應是樹,節點i至j的路徑為唯一
// (3) 應該還有更好的方法,找每2節點之間距離,我用bfs,請熱心人士提供較佳解法
// (4) 找出每2節點的距離後, 計算 sumof(每兩節點i至j的距離 {i<j} ),再乘2即可

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int maxn = 1010;
int d[maxn][maxn];
vector<int> v[maxn];
queue <int> q;
bool used[maxn];

void bfs(int s)
{
int k=q.front();
q.pop();
for(int i=0; i<v[k].size(); ++i) // 所有 k 的相鄰點
{
int j=v[k][i];
if(!used[j])
{
used[j]=true;
q.push(j);
if(!d[s][j]) d[s][j] = d[s][k]+d[k][j];
}
}
if(!q.empty()) bfs(s);
}

int main()
{
  int i,j,k , n,t;
  int a,b,c;
  cin >> t;
  while(t--)
  {
  cin >> n;
  memset(d,0,sizeof(d));
  for(i=1;i<=n;++i) v[i].clear();
for(i=1;i<n;++i)
{
cin >> a >> b >> c;
d[a][b] = d[b][a ]= c;
v[a].push_back(b);
v[b].push_back(a);
}
  for(int s=1; s<=n; ++s)
  {
  memset(used,0,sizeof(used));
q.push(s); used[s]=true;
bfs(s);  // 節點 s 至其它節點的距離 d[s][k], k=1~n
}
int sum=0;
for(i=1;i<n;++i)
for(j=i+1;j<=n;++j)
sum += d[i][j];
cout << 2*sum << endl;
}
  return 0;
}
/*
範例輸入:
4
5
1 2 5
2 3 10
3 4 3
3 5 1
2
1 2 10
7
6 1 9
1 5 5
1 3 8
3 2 7
5 4 6
4 7 3
7
6 1 9
1 5 5
5 3 8
3 2 7
5 4 6
4 7 3
範例輸出:
192
20
628
608
*/

19
NPSC2004國中組決賽 / NPSC 2004 國決 F.星光大道
« 於: 五月 15, 2015, 10:20:29 pm »
代碼: [選擇]
// npsc04-j2f (NPSC 2004 國中決 題目 F 星光大道)
// 將 ci/li 做 sort ,由最小的開始選用,至 所有 l0+l1+...lk的和 >=L 為止 , 最後一個 lk不一定用完哦
// 若用完所有的布仍不夠{即 L還有剩,則 印 Oh, NO!}
//

#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
const int maxn = 10010;
struct node
{

int e; // 布長
int c; // 價錢
double d; // 平均價
} a[maxn];
bool cmp( node x, node y)
{
return x.d < y.d;
}
int main()
{
  int i, t, L , n;
  unsigned k;
cin >> t;
while(t--)
{
cin >> L >> n;
for(i=0;i<n;++i)
{
cin >> a[i].e >> a[i].c;
a[i].d = double(a[i].c) / a[i].e;
}
sort(a, a+n , cmp);
double tot=0.0;
for(i=0; i<n; ++i)
{
if(L>=a[i].e)
{
L -= (a[i].e);
tot += (a[i].c);
} else { 
tot += (L * a[i].d);
L=0;
break; // 已舖滿 L
}
}
if(L>0) cout << "Oh, No!" << endl;
else cout << fixed << setprecision(2) << tot << endl;
}
  return 0;
}
/*
範例輸入:
3
10 2
5 2
5 3
10 2
6 2
5 3
10 2
1 1
1 1
範例輸出:
5.00
4.40
Oh, No!
*/


20
NPSC2004國中組決賽 / npsc 2004國決 E.排順序
« 於: 五月 15, 2015, 08:52:35 pm »
代碼: [選擇]
// npsc04-j2e (2004國中決 題目 E 排順序)
// 模擬 qsort 遞迴,有swap時印出所有陣列

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
const int maxn = 210;
int a[maxn];
int n;   // n 筆資料
void qsort(int lt, int rt)
{
if(lt==rt) return; // 如果只有一個就排好了
int lt0=lt, rt0=rt;
int x=a[lt] , t;
while( lt <rt )
{
while(a[lt]<x) ++lt; //左手比 x 小,往右移
while(a[rt]>x) --rt; //右手比 x 大,往左移
if(lt<rt)  // 左手 在 右手 的左邊
{
t=a[lt]; a[lt]=a[rt]; a[rt]=t;  //swap , 有交換 就印
cout << a[0]; for(int i=1; i<n; ++i) cout << " " << a[i];  cout << endl;
++lt;  --rt;
}
}
// 當左手 不在 右手 的左邊,就分組
qsort(lt0 , rt);  // 將右手及其左邊 分一組
lt = rt+1;
qsort(lt , rt0);  // 將右手的右邊  分一組
}

int main()
{
  int t ;
cin >> t;
while(t--)
{
cin >> n;
for(int i=0; i<n; ++i) cin >> a[i];
qsort(0,n-1);
cout << endl; //每一組後印一空白列
}
  return 0;
}
/*
輸入範例:
2
8
4 6 7 8 5 2 3 1
4
4 3 2 1
輸出範例:
1 6 7 8 5 2 3 4
1 3 7 8 5 2 6 4
1 3 2 8 5 7 6 4
1 2 3 8 5 7 6 4
1 2 3 4 5 7 6 8
1 2 3 4 5 6 7 8

1 3 2 4
1 2 3 4

*/


頁: [1] 2 3