NPSC補完計劃

登入註冊帳號.

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

最新消息:

歡迎光臨NPSC補完計劃

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

顯示文章

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

主題 - rscpp

頁: 1 [2] 3
21
NPSC2004國中組決賽 / NPSC 2004國決 B 化學元素組成
« 於: 五月 07, 2015, 09:33:52 pm »
代碼: [選擇]
// npsc04-j2b (2004國中決 題目 B 化學元素組成)
// 題目說每組有4個整數 1<= wi1 , wi2 , pi1 , pi2 <=100 ,沒說 wi1會不會等於wi2,若相等應只有一組 w1輸出
// 我們先處理使wi1<wi2, 輸出的w1(wi1+wi1):w2(wi1+wi2):w3(wi2+wi2),題目說w1<=w2<=...<=w? 又說互異,應該是若相等的需合成一個?
// 因wi1,wi2只有兩個,wi1 != wi2則有三種不同w1(wi1+wi1):w2(wi1+wi2):w3(wi2+wi2),若wi1 == wi2 則只有一種w1(wi1+wi2) p為1
// wi1 != wi2 的三種 p 值(p1=pi1xpi1 , p2=2xpi1xpi2 , p3=pi2xpi2) 註:pi1,pi2也隨wi1,wi2的大小調整哦,最後p1,p2,p3求gcd化簡
#include <iostream>
#include <cstring>
using namespace std;
int gcd(int a, int b)
{
int r;
while( r=a%b )
{
a=b;
b=r;
}
return b;
}
int main()
{
  int t,i,j,n,cas;
  int wi1,wi2,pi1,pi2;
cin >> n;
for(cas=1; cas<=n; ++cas)
{
cin >> wi1 >> wi2 >> pi1 >> pi2;
if(wi1==wi2)
{
cout << "Case " << cas <<"-> " << wi1+wi2 << " = 1\n";
continue;
}
if(wi1>wi2)
{
t=wi1; wi1=wi2; wi2=t;
t=pi1; pi1=pi2; pi2=t;
}
int p1=pi1*pi1 , p2=2*pi1*pi2 , p3=pi2*pi2;
int g=gcd(p1, gcd(p2,p3));
cout << "Case " << cas <<"-> "
<< wi1+wi1 << " : "  << wi1+wi2 << " : " << wi2+wi2 << " = "
<< p1/g << " : "  << p2/g << " : " << p3/g << endl;
}
  return 0;
}
/*
範例輸入:

4
1 2 1 1
16 17 2 2
37 35 1 3
50 50 2 5
範例輸出:

Case 1-> 2 : 3 : 4 = 1 : 2 : 1
Case 2-> 32 : 33 : 34 = 1 : 2 : 1
Case 3-> 70 : 72 : 74 = 9 : 6 : 1
Case 4-> 100 = 1
*/

22
NPSC2004國中組決賽 / NPSC 2004國決 A 彩紙片片
« 於: 五月 07, 2015, 08:49:07 pm »
代碼: [選擇]
// npsc04-j2a (2004國中決 題目 A 彩紙片片)
// n 張彩紙,依其位置在公告欄的每1小格計數,所需執行的次數粗估如下
// t<=15, n<=1000, 每張海報<= 100x100, ( 15 x (清公告欄(1000x1000)) + (貼彩紙(1000x100x100)) ) <= 1.65 * 10^8
// 要看測資,不曉得會不會逾時, 但我只想得到這個方法,不曉得有沒有更快的方法?
#include <iostream>
#include <cstring>
using namespace std;
const int maxn=1010;
int bd[maxn][maxn];
int main()
{
  int i,j,A,B,t;
cin >> t;
while(t--)
{
cin >> A >> B;
for(i=A;i>=0;--i)
   for(j=B;j>=0;--j)
    bd[i][j]=0;
int x,y,w,h,n, m=0;
cin >> n;
while(n--)
      {
cin >> x >> y >> w >> h;
for(i=x+w-1; i>=x; --i)
for(j=y+h-1; j>=y; --j)
if( ++(bd[i][j]) > m ) m = bd[i][j];
}
cout << m << endl;   
}

  return 0;
}
/*
範例輸入:
2
10 10
5
1 1 2 3
2 4 3 5
1 3 2 4
9 9 1 1
0 0 1 1
11 11
7
3 1 4 7
1 2 9 3
2 3 3 3
6 3 3 4
3 7 3 2
6 0 2 4
6 3 1 5
範例輸出:
2
5
*/


23
NPSC2004國中組初賽 / E 排排站
« 於: 四月 19, 2015, 11:32:54 am »
好像在神人劉汝佳的書中有提到「鍵結結構-例題-移動小球」寫過一次,有移前及移後,
這題只是移後,應較簡單,程式要找一下再後補,找到了:
輸入第1行2個數字 ,球數n、指令數m ,指令兩種 A x y及B x y,將x移至y之前及之後
以下為移動小球的程式碼,而 NPSC 2004 國中 E排排站只有將 x  移至 y之後,應直接改一下即可
代碼: [選擇]
// 提升程式設計的邏輯思考力 p6-7~6-9 例6.2.1 移動小球 解法 B 鏈式串列
// 指令 A x y 將x移至y之前, B x y 將x移至y之後
#include <iostream>
using namespace std;
const int MaxN = 500000 ;  // 最多 50 萬 顆球
int lt[MaxN+1]; // 左 link
int rt[MaxN+1]; // 右 link
int n; // 小球 的數量

int main( )
{
int m; // 指令數 <= 100000
cin >> n >> m; // 輸入球數 、指令數
int  i ,f=1,r=n;
   lt[1]=-1; for(i=2; i<=n; ++i) lt[i]=i-1; // 左鍵
   rt[n]=-1; for(i=n-1; i>=1; --i) rt[i]=i+1; // 右鍵
   char c; // 指令
   int x,y; //移動的球號、目標的球號
   int a , b;
while( m-- )
{
cin >> c >> x >> y;
// 將 x 移出
a=lt[x] ; b=rt[x];   // x 的左a 及 右b
if(a<0) lt[b]=-1, f=b;
else if(b<0)  rt[a]=-1 , r=a;
else lt[b]=a , rt[a]=b;
// 將 x 插入 y 之左 或 之右
if( c == 'A' ) {  // 將 x 插入 y 之左
a=lt[y] ;
lt[x] = a; lt[y] = x;
rt[x] = y;
if(a==-1) f=x; else  rt[a] = x;
} else { // 將 x 插入 y 之右
b=rt[y];
lt[x] = y;
if(b==-1) r=x; else lt[b] = x;
rt[x] = b; rt[y] = x;
}
}
cout << f;
   while( rt[f]>0 )
   {
f = rt[f];
cout << " " << f ;
}
cout << endl;
 
   return 0;
}
/*
6 2
A 1 4
B 3 5
6 3
B 1 6
B 2 1
A 5 2
-----------
2 1 4 5 3 6
3 4 6 1 5 2
*/


24
NPSC2004國中組初賽 / D 碰碰狸歷險記
« 於: 四月 19, 2015, 11:27:43 am »
代碼: [選擇]
// npsc04-j1d 碰碰狸歷險記
// 六角形每邊長1、中心點至各頂點為1、中心至邊的垂直距 sqrt(0.75)=0.8660254
// 上下移 (0,±1.73205) 、 斜線移( ±1.5 , ±0.86603)、橫移需成對的斜移來完成
// 先斜移至x軸或y軸(min(x/1.5, y/0.86603) ),再直接算橫移的步數(x/1.5)或直移的步數(y/1.73205)
// 直接將輸入的 x,y 取絕對值÷1.5及÷0.8660254後四捨五入取整數步數來處理
*/
#include <iostream>
#include <cmath>
using namespace std;
const double sx=1.5 , sy=0.8660254;
int main()
{
double dx,dy;
int n;
int x,y,m,ans;
while( cin >> n )
{
while(n--)
{
cin >> dx >> dy;
x = int(fabs(dx)/sx+0.5); //轉成以 1.5 為單位的步數
y = int(fabs(dy)/sy+0.5); //轉成以 0.8660254 為單位的步數
m = min(x,y);  //斜移至軸線的步數
ans = m+1 + max(x-m, (y-m)/2);
// cout <<"x,y,m: ans"<<x<<","<<y<<","<<m<<": "
cout << ans << endl;
}
}


  return 0;
}
/*
---------------範例輸入:
2
1.5 0.866
4.5 4.330
3
1.5 6.062178
6 3.464102
7.5 2.598076
1
-4.5 0.866
-----------------範例輸出:
2
5
5
5
6
*/

25
NPSC2004國中組初賽 / C 現在幾點
« 於: 四月 19, 2015, 11:23:49 am »
時區名可能1個word或2個word 接著才是倒數的秒數,所以用 istringstream讀資料
另時區名轉成與倫敦的時差,以map實作
代碼: [選擇]
// npsc04-j1c (NPS 2004 國中初 C 現在幾點)
// 第1列 n ,接下來會有 N 行,每行會有一個城市 s 和一個數字 t,(城市名 X 可能由兩字串組成) 此城市還剩下 t 秒會結束這一天 ( 0 <= Y <= 86400 )
// 由城市名查map得出m小時,(-m*3600+8*3600)-t 換算台灣時間的秒數,避免負數+2個24*60*60之後再mod, 以 h m d 顯示
//
#include <iostream>
#include <map>
#include <sstream>
#include <cstring>
using namespace std;
map<string , int> tmap;
void init()  // 建時區表查詢用 map
{
tmap["London"] = 0; tmap["Playa"] = -1; tmap["Trinidade"] = -2;
tmap["San Diego"] = -3; tmap["Hamilton"] = -4; tmap["New York"] = -5;
tmap["Chicago"] = -6; tmap["New Mexico"] = -7 ; tmap["Los Angeles"] = -8;
tmap["Anchorage"] = -9; tmap["Hawaii"] = -10; tmap["Midway Island"] = -11;
tmap["Vienna"] = 1; tmap["Athens"] = 2; tmap["Moscow"] = 3 ;
tmap["Abu Dhabi"] = 4 ; tmap["Islamabad"] = 5 ; tmap["Colombo"] = 6;
tmap["Bangkok"] = 7; tmap["Taiwan"] = 8; tmap["Tokyo"] = 9;
tmap["Melbourne"] = 10; tmap["Noumea"] = 11; tmap["Auckland"] = 12;
}
int main()
{
init();
int n,i,t,m;
string line,s[4];
cin >> n;   getline(cin,line);
while( n-- )
{
getline(cin,line);
istringstream ss(line);
i=0;
while( ss >> s[i])++i;
if(i==3)
{
  istringstream st(s[2]);
  m=tmap[(s[0]+" "+s[1])];
  st >> t;
}else{
  istringstream st(s[1]);
  m=tmap[s[0]];
  st >> t;
}
t=(201600-m*3600-t)%86400;  // 28800+86400+86400 = 201600
cout << t/3600 << " " << (t%3600)/60 << " " << t%60 << endl;
}
  return 0;
}
/*
------------------範例輸入:
5
London 100
Hawaii 1000
San Diego 1234
Midway Island 86300
Auckland 85200
----------------範例輸出:
7 58 20
17 43 20
10 39 26
19 1 40
20 20 0
*/

26
NPSC2004國中組初賽 / B 對稱的棋盤
« 於: 四月 18, 2015, 11:38:14 pm »
代碼: [選擇]
/*
// npsc04-j1b (2004國中初賽 B對稱的棋盤)
// 圍棋棋盤每格的 編號 (A~T,1~19),輸入第1行一個數字 n ,接著n格的編號,輸出其對稱點編號
// 解題說明:i對稱的編號 20-i ,將A~T[沒有I」分別代入1~19同理

*/
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
string a="ABCDEFGHJKLMNOPQRST"; //沒有 I
   int n,i,k;
   string s;
   while( cin >> n )
   {
while(n--)
{
cin >>s;
i=a.find(s[0]);
k=int(s[1]-48);
if(s.size()==3) k=k*10+(s[2]-48);
cout << a[18-i] << 20-k << endl;
}
}
  return 0;
}
/*
4
A19
B18
C4
Q5
--------
T1
S2
R16
D15
*/

27
NPSC2004國中組初賽 / A 便利商店
« 於: 四月 18, 2015, 10:44:53 pm »
代碼: [選擇]
// npsc04-j1a 便利商店
// 多組資料,每組第1行 n ,有n種商品,接著 n 行{商品名 價錢},第n+1行一個數字m,有m個顧客,接著m行為顧客所購買的商品資訊
// 每行購買的商品資訊為第1個數字 k 代表共購買了k種商品,接著k對{商品名 數量}
// 對每一位顧客,輸出其購買金額
*/
#include <iostream>
#include <map>
using namespace std;
map<string, int> com; //商品名,價錢
int main()
{
   int i,j,k,n,m,p,q;
   string s;
   while( cin >> n )
   {
com.clear();
while(n--)
{
cin >> s >> p;  //商品名、價錢
com[s]=p;
}
cin >> m;
while(m--)  // m 個顧客
{
int ans=0;  //總購買金額
cin >>k;    // 買了k種
while(k--)
{
cin >> s >> q ; // s商品買了 q 個
ans += ( com[s]*q ); //由 com 查出商品 s 的價錢
}
cout << ans << endl;
}
}
   return 0;
}
/* ------------範例輸入
3
abc 50
xyz 70
opq 66
2
2 abc 2 opq 3
3 xyz 5 abc 6 opq 7
5
potato 40
chocolate 100
pen 45
coke 30
water 20
2
3 pen 2 coke 5 water 1
2 chocolate 5 bicycle 1
-------------------範例輸出:
298
1112
260
500

*/

28
NPSC2003國中組決賽 / F 資料蒐集
« 於: 四月 18, 2015, 10:03:08 pm »
代碼: [選擇]
// npsc03-j2f 資料蒐集
// 第一行t,有t組資料,每組有3行 代表3個人所蒐集的資料,每一列第1個數字 n ,接著 2n個數字,代表n個選手的安打數、背號
// 3人所蒐集的選手背號皆不同,但安打數有可能相同,三人資料彙整後,依安打數由小至大列出選手背號,安打數相同依背號由小至大
#include <iostream>
#include <cstring>
#include <map>
#include <set>
using namespace std;
map<int,int> gid; //由安打數 查序號
map<int,int>::iterator mit;
set<int> glist[301]; // 最多300人,每個選手一個
set<int>::iterator sit; //
int main( )
{
   int  t,n,m,i , j , k, gcnt;
   int bn , hn; //背號、安打數
   cin >> t;
   while( t-- )
   {
gcnt=0; gid.clear();
for(i=0;i<301;++i) glist[i].clear();
for(i=0; i<3; ++i) //讀入三人的資料
{
cin >> n;  //n個選手
while(n--)
{
cin >> bn >>hn;  //背號、安打數
k = gid[hn]; //將安打數 轉成 序號 k
if(k==0) k = (++gcnt);  //若未出現過,序號+1
gid[hn]=k;
glist[k].insert(bn); //將選手背號 加入此安打數的 清單中
} // end of while(n-- n 個 選手
} //  end of for(i=0~2 , 三人的資料
// 接著依 gid安打數由小至大將有的序號找出,再依序號將選手背號印出
for(mit=gid.begin(); mit!=gid.end(); ++mit)
{
k = (mit->second);
for(sit=glist[k].begin(); sit!=glist[k].end(); ++sit)
cout << (*sit) << " ";
}
cout << endl;
}
   return 0;
}
/* 範例輸入
3
3 33 5 22 6 11 3
5 55 3 66 7 77 2 15 6 7 6
4 88 9 99 7 9 1 18 0
1 9 1
1 8 2
2 6 3 7 2
3 52 1 17 7 28 13
6 50 0 43 2 19 3 41 4 38 5 99 10
3 24 8 71 11 15 15
-------輸出
18 9 77 11 55 33 7 15 22 66 99 88
9 7 8 6
50 52 43 19 41 38 17 24 99 71 28 15
*/


29
NPSC2003國中組決賽 / E 清單
« 於: 四月 18, 2015, 05:13:47 pm »
代碼: [選擇]
// npsc03-j2e 清單
// 多組資料,每組第1行 n {若n=0結束),接下來n 行,boy m g1 g2 ... gm , boy為男生名,g1,...gm為 m 個女生名
// 每組的第 n+1行一個女生名,輸出其所認識的男生(依字典序)
#include <iostream>
#include <cstring>
#include <map>
#include <set>
using namespace std;
map<string,int> gid; //由姓名查序號
set<string> glist[40]; // 最多40人,每個女生一個,存其所認識的男生
set<string>::iterator it; //
int main( )
{
   int  n,m,i , j , k, gcnt;
   string boy,girl;
   while( cin >> n)
   {
if(n==0) break;
gcnt=0; gid.clear();
for(i=0;i<40;++i) glist[i].clear();
while(n--)
{
cin >> boy >> m;  //某個男生,認識 m 個女生
for(i=0; i<m; ++i)
{
cin >> girl;  //m 個女生之一名
k = gid[girl]; //將姓名轉成序號 k
if(k==0) k = (++gcnt);  //若未出現過,序號+1後當成此女生的序號
// cout <<"["<<k<<"i:"<<boy<<"] ";
gid[girl]=k;
glist[k].insert(boy); //將男生名加入此女生的 清單中
} // end of for(i=0~m-1 m 個 女生
} // end of while(n-- n 個 男生
// 接著讀入要查詢的女生名,查出其序號 k,再由 glist[k]列出其所認識的男生
cin >> girl;
k = gid[girl];     // 若為0沒男友,未說明如何處理 cout <<k<<glist[k].size()<<endl;
for(it=glist[k].begin(); it!=glist[k].end(); ++it)
cout << (*it) << " ";
cout << endl;
}
   return 0;
}
/* 範例輸入
3
Npsc 3 Forum Hello World
Abcdefg 0
Zero 1 Hello
Hello
5
D 3 O X Z
E 3 P Q X
B 3 K W X
C 3 V W X
A 3 X Y Z
X
-------輸出
Npsc Zero
A B C D E
*/


30
NPSC2003國中組決賽 / D 名字倒過來寫
« 於: 四月 18, 2015, 05:13:03 pm »
代碼: [選擇]
// npsc03-j2d 名字倒過來寫
// 第1行 n ,接下來n行,每行最多20英文字,第1字母大寫,餘小寫,倒印(但倒印的第1個字母改大寫,最後1字改小寫)
//
#include <iostream>
#include <cstring>
using namespace std;
int main( )
{
   int  n , i , s;
   string m;
   while( cin >> n)
   {
while(n--)
{
cin >> m;
s=m.size();
cout << char( m[s-1]-32 );  // 改大寫
for(i=s-2; i>0; --i)
  cout <<m[i];
cout << char( m[0]+32 ) << endl;  // 改小寫
}
}
   
   return 0;
}
/* 範例輸入
5
Npsc
Forum
Hello
World
Abcdefg
-------輸出
Cspn
Murof
Olleh
Dlrow
Gfedcba
*/


31
NPSC2003國中組決賽 / C 多邊形
« 於: 四月 18, 2015, 05:12:20 pm »
代碼: [選擇]
// npsc03-j2c 多邊形
// 有多筆資料,一筆一列,每列第1個 3<=n<=6 ,接著 n 個數字 {沒規定,假設 -999~999好了},若n=0結束測資
// 判斷 n 邊形的 n 個角度是否正確,正確輸出correct、否則incorrect,角度>0且<360才正確
#include <iostream>
using namespace std;
int t[]={0,0,0,180,360,540,720}; // n 邊形的總角度和
int main( )
{
   int  n , i , j ,k , s;
   while( cin >> n)
   {
if(n==0) break;
s=0;  // 輸入的 n 個角總和
for(i=0;i<n;++i)
{
cin >> k;
if(s>t[n]) continue;  // 目前為止內角已超出
if( k<=0 ) s=999; //六邊形最大720
else s+=k;
}
// cout <<i<<":"<<s <<"  ";
if(s==t[n]) cout <<"correct" << endl;
else  cout <<"incorrect" << endl;
}
   
   return 0;
}
/* 範例輸入
3 30 60 90
4 90 90 90 80
5 60 60 300 60 60
6 120 -60 420 60 60 120
0
-------輸出
correct
incorrect
correct
incorrect
*/


32
NPSC2003國中組決賽 / B 石板
« 於: 四月 17, 2015, 04:23:57 pm »
題目大意:一條路共有100個石板,最多10人走過,起點一定是第1塊,
 每人的步距不一,可以1~100,步距2的會踏到1,3,5,...99,距50的1,51
 輸入第一行有一個數字t,代表t組資料,接著2*t列,每組2列
 每組的第1列n,代表有n個人(1<=n<=10),第2列n個數字Li,代表
 這n個人的步距1<=L1~Ln<=100
 每一組資料輸出一列(1個數字),這100塊石板被踩到最多下的有幾塊

解題:n個步距的最小公倍數 g,則ans = 99/g+1
這題若測資 t 不大就沒問題,但若太大呢?

所以我決定先跑一個100x100的lcm[][]:1~100兩兩的最小公倍數
每組的n個數字,前1個a, 後1個b
cin >>a; 
for(i=1;i<n;++i)
{
  cin >> b;
  a = lcm[a][ b];
}
a 即是這 n 個數字的最小公倍數
代碼: [選擇]
/*
npsc03-j2b 石板
題目大意:一條路共有100個石板,最多10人走過,起點一定是第1塊,
 每人的步距不一,可以1~100,步距2的會踏到1,3,5,...99,距50的1,51
 輸入第一行有一個數字t,代表t組資料,接著2*t列,每組2列
 每組的第1列n,代表有n個人(1<=n<=10),第2列n個數字Li,代表
 這n個人的步距1<=L1~Ln<=100
 每一組資料輸出一列(1個數字),這100塊石板被踩到最多下的有幾塊

解題:n個步距的最小公倍數 g,則ans = 99/g+1
這題若測資 t 不大就沒問題,但若太大呢?
所以我決定先跑一個100x100的lcm[][]:1~100兩兩的最小公倍數
每組的n個數字,前1個a, 後1個b
cin >>a; 
for(i=1;i<n;++i)
{
  cin >> b;
  a = lcm[a][b];
}
a 即是這 n 個數字的最小公倍數
*/
#include <iostream>
#include <sstream>
#include <cstring>
using namespace std;
int gcd(int a, int b)
{
int r;
while( r=a%b )
{
a=b;
b=r;
}
return b;
}
int lcm[101][101];
int main()
{
  int i,j,k;
memset(lcm,0,sizeof(lcm));
lcm[100][100]=100;
for(i=1; i<100; ++i)
{
lcm[i][i]=i;
for(j=i+1; j<=100; ++j)
{
if(lcm[i][j]!=0) continue;
k=i*j;
lcm[i][j] = lcm[j][i] = k/gcd(j,i);
}
}
int t,n,a,b;
cin >> t;
while(t--)
{
cin >> n;
cin >> a;
for(i=1;i<n;++i)
{
  cin >> b;
  a = lcm[a][b];
}
cout << (99/a+1) << endl;
}
  return 0;
}
/*
4
1
2
1
5
2
2 3
3
2 3 5
-----------
50
20
17
4
*/


33
NPSC2003國中組決賽 / A 數饅頭
« 於: 四月 17, 2015, 04:10:16 pm »
題目大意:第1行0<=n<=365假日的個數,接著n列為n個日期 m d
第n+2列為一個數字s代表有s個學期,然後有s列,各八個數字
y1 m1 d1 w1 y2 m2 d2 w2 每學期的開學日及結束日
1900<=y1,y2 、1<=m1,m2<=12、 1<=d1,d2<=12、
1<=w1,w2<=7{代表星期一~星期日}
每週六、日不用上課,假日也不用上課,請問每學期上課天數

解題方式:因為沒說明一學期是否會超過一年(365天以上),若不會的話
     100組*366程式用列舉每一天看是否為假日來計數應該可以使用每一天判斷的方式,程式碼如下
代碼: [選擇]
// NPSC 2003 國決 A 數饅頭
#include <iostream>
using namespace std;
bool isleap(int y)  // 是否閏年
{
  return (y%400==0) || (y%4==0 && y%100!=0);
}
bool hd[13][32]; // 假日則為true
int md[]={366,31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 }; // 12個月的日期,以366日計
int count( int m1,int d1,int m2,int d2, int *w1)
{
int mi, di, wi = *w1-1, ans=0;  // wi 星期改為 0~6
for(di=d1; di<=md[m1]; ++di, wi=(wi+1)%7 )  // m1月的剩下日期
if( !(wi==5 || wi==6 || hd[m1][di]) ) ++ans;  // 非假日,要上課
for(int mi=m1+1; mi<m2; ++mi)
for(di=1; di<=md[mi]; ++di, wi=(wi+1)%7)  // m1+1 ~ m2-1 月各月的上課日
if( !(wi==5 || wi==6 || hd[mi][di]) ) ++ans;  // 非假日,要上課
if( m2>m1)
  for(di=1; di<=d2; ++di, wi=(wi+1)%7 )  // m2月到d2日之前的日期
if( !(wi==5 || wi==6 || hd[m2][di]) ) ++ans;  // 非假日,要上課
  *w1 = (wi+1);  // 傳回下一日的 w1(改回 1~ 7)
return ans;
}
int main()
{
  int i,n,m,d,s;
  // 假日
  memset(hd,0,sizeof(hd));
  cin >>n;
  for(i=0;i<n;++i)  //
  {
cin >> m >> d;
hd[m][d]=true;
  }
  cin >> s;  // 學期數
  int  y1,m1,d1,w1, y2,m2,d2,w2;
  for(i=0; i<s; ++i)
  {
cin >> y1 >> m1 >> d1 >> w1
>> y2 >> m2 >> d2 >> w2 ;
// 假設開學日在前、結束日在後 ,且一學期不會超過一年
int ans = 0;
if(y1==y2)
{
if( isleap(y1) ) md[2]=29; else md[2]=28;
ans = count(m1,d1,m2,d2,&w1);
} else {
if( isleap(y2) ) md[2]=29; else md[2]=28;
   ans = count(m1,d1,12,31,&w1);
ans += count(1,1,m2,d2,&w1);
}
cout << ans  <<endl;
}
  return 0;
}

但我想寫一個可以超過一年以上的學期{如果要給個期限,就最多一萬年}
另如果開學日比結束日晚或中間都是假日就是0天不會有負的
程式碼另補吧!
想了幾個方式,都不是很滿意,目前的想法是建7x2的整年上課的日數表ytot[7][2]
分別為該年元日為週一~週日的上課日數,又分平閏年:ytot[0][0]元旦為週一的平年
ytot[0][1]為週一閏年,ytot[1][0]為週二平年,ytot[1][1]為週二閏年…
有了這個表應可以計算 y1+1 ~ y2-1之間的上課日數,公式及程式碼懶得做,
留給熱心的「補完人」來補完吧, 應有更好的方式,期待熱心人士。

34
NPSC2001國中組決賽 / 題目A 33倍數+1 (C++)
« 於: 四月 14, 2015, 01:54:53 pm »
代碼: [選擇]
// npsc01-j2a (2001 國決 題目 A  33N+1)
// 每列一串數字,最長 250 位數, 0 結束 ,若33的倍數+1 則印  T 否則印 F
//  33的倍為為 3的倍數且11的倍數, 3:所有位數被3整除、 11:奇偶位數和的差被11整除
//  大數 -1 也是可以算出奇、偶位的數字和
#include <iostream>
using namespace std;
int main()
{
  string s;
  while( cin >> s)  // 假設測資中 s 無前導0及前後空白,否則應另處理
  {
    if(s[0]=='0') break;
    int sum[2]={0,0};  // 奇位及偶位的和
    int sw=0;  // 0奇、1偶
    int sn = s.size();
    int i,z;
    for(i=sn-1; i>=0; --i, sw=1-sw)  sum[sw] += ( s[i]-'0' );  // 算奇偶位的和
  //  cout << sum[0] <<"," << sum[1] << " || ";
    // 大數減法 -1 ,除非末端為 0 否則直接-1(奇位-1)
    // 末端(1個0:奇位+9偶位-1)、(2個0:奇位+9-1偶位+9)、(3個0:奇位+9*2偶位+9-1)、(4個0:奇位+9*2-1偶位+9*2)…
    for(z=0, i=sn-1; i>=0; --i)
       if(s[i]!='0') break; else ++z;
    if(z>0) {  // 末端有0時
      sum[0] += ( (z+1)/2*9 );  sum[1] += ( z/2*9 ); //z個0: (奇位+(z+1)/2個9、偶位+z/2個9)再扣掉借位的
      sum[ z%2 ] -= 1;  // 末端0的個數: 奇個0偶位-1、偶個0奇位-1
    } else sum[0]--;  // 未端非0 直接奇位 -1 
    // 奇數位的和 sum[0] , 位數的和 sum[1]
//       cout << sum[0] <<"," << sum[1] << endl;
    // 若(odd+even)%3 ==0 且 abs(odd-even)%11==0) 且被33整除
    if( (sum[0]+sum[1])%3==0 && abs(sum[0]-sum[1])%11==0 )
       cout << "T" << endl;
   else cout << "F" << endl;
  }
  return 0;
}
/*
{12345678987654321*33 = 407407406592592593   ,
18446744073709551616*33 = 608742554432415203328 }
  範例輸入
33
34
3433
34343430
34343431
407407406592592592
407407406592592593
407407406592592594
608742554432415203328
608742554432415203327
608742554432415203329
132000
45600
0
  範例輸出
F
T
T
F
T
F
F
T
F
F
T
F
F
*/

35
NPSC2001國中組初賽 / 題目 E 撿石頭 (C++)
« 於: 四月 14, 2015, 01:36:51 pm »
代碼: [選擇]
// npsc01-j1E (2001 國初 題目 E 撿石頭)
// 第1列 n 有n組資料,每一組第1列m為有m個數字(數字有可能為負) 
// 最長遞增子序列, 因 m高達 10^5又不需列出序列,故 m^2的方法不可行
// LIS nlogn , 此方法只可求長度,無法列出序列
// 參考 http://fanli7.net/a/bianchengyuyan/C__/20140524/507756.html
// 解法說明參考:http://tc.wangchao.net.cn/bbs/detail_59352.html

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int a[100005];   // 存目前為止遞增列可放入的資料
int main() {
   int n, m;
// while (~scanf("%d", &n)) {  // 若資料量太大也可能需改為scanf
   cin >> n;
   while( n-- )
   {
       cin >> m;   // 每一組資料 m 個數字(有可能負數)
       int now = 0;  // 目前的長度
       cin >>a[now];  //scanf("%d", &a[now]);
       --m;   // 第1筆
       while (m--)  // 接著第2筆之後的 
       {
          int num;
          cin >> num;   //scanf("%d", &num);
          if (num > a[now]) a[++now] = num;   // 若比目前的最後一個大,加至後面
          // 否則,在a中找到 >= num 的最左一格 放入 num
          else *lower_bound(a, a + now, num) = num;
       }
       cout << now+1 << endl;  // 因由0開始 ,長度加1 //printf("%d\n", now + 1);
   }
   return 0;
}
/*
5
5
1 2 3 4 5
5
5 4 3 2 1
7
1 9 10 5 11 2 13
2
2 -1
11
1 9 10 5 6 11 7 8 2 13 14
-------------------
5
1
5
1
7
*/


36
NPSC2001國中組初賽 / A 裝箱子 (C++)
« 於: 四月 14, 2015, 12:11:27 am »
代碼: [選擇]
/*  (2001 國初 題目 A 裝箱子)
// 每列4個數字,前2為第1個矩形的長、寬,後2為第2個矩形的長、寬, 不一定哪一個較大,不考慮厚度及斜放,問是否某一矩形可裝入另一個
// 解答方向,先確認兩個矩形的小邊、大邊, 1小<=2小且1大<=2大則1可裝在2之內,或1小>=2小且1大>=2大 則2可裝在1之內
*/
#include <iostream>
using namespace std;
int main()
{
  int x1,y1,x2,y2,t;
while( cin >> x1 )
{
if(x1==0) break;
cin >> y1 >> x2 >> y2;
if(x1>y1) { t=x1 ; x1=y1; y1=t; }
if(x2>y2) { t=x2 ; x2=y2; y2=t; }
if( (x1<=x2 && y1<=y2) || (x1>=x2 && y1>=y2) )
cout << "yes" << endl;
else cout << "no" << endl;
}
  return 0;
}
/*
範例輸入
2345 6789 12345 16789
1 100 50 2
0
範例輸出
yes
no

*/

37
NPSC2001國中組初賽 / D 費波那契數的遞迴展開(C++)
« 於: 四月 13, 2015, 11:50:45 pm »
代碼: [選擇]
/*
// npsc01-j1d (2001 國初 題目 D 費波那契數的遞迴展開 )
// 輸入 n 、接著n個數字0<=ai<=45,以遞迴呼叫 f(a)所需遞迴的呼叫次數,以 f(4)為例共需 9 次
//       f(4)
//        f(3)  +    f(2)
//    f(2) + f(1)  f(1)+f(0)
// f(1)+f(0)
// 解題說明,對於每一個 f(k)的呼叫次數 h(0)=h(1)=1,而k>=2的 h(k)=h(k-1)+h(k-2)+1
// 先算出 0 ~ 45 的h(k) 然後查表  h[45] 用unsigned就夠
0:1 1:1 2:3 3:5 4:9 5:15 6:25 7:41 8:67 9:109 10:177
11:287 12:465 13:753 14:1219 15:1973 16:3193 17:5167 18:8361 19:13529 20:21891
21:35421 22:57313 23:92735 24:150049 25:242785 26:392835 27:635621 28:1028457 29:1664079 30:2692537
31:4356617 32:7049155 33:11405773 34:18454929 35:29860703 36:48315633 37:78176337 38:126491971
39:204668309 40:331160281 41:535828591 42:866988873 43:1402817465 44:2269806339 45:3672623805
*/
#include <iostream>
using namespace std;
int main()
{
 unsigned int h[46];
 int i,n,a;
  h[0]=h[1]=1;
   for(i=2;i<=45;++i)
   {
h[i] = h[i-1]+h[i-2]+1;
// cout <<i<<":"<< h[i]<<endl;
   }
   cin >> n;
   while(n--)
   {
cin >>a;
cout << h[a] << endl;
}

  return 0;
}
/*
範例輸入
7
0
1
2
3
4
5
45
  範例輸出
1
1
3
5
9
15
3672623805

*/

38
NPSC2014國中組決賽 / NPSC 2014 國中組決 B. 半折植樹
« 於: 一月 24, 2015, 08:39:55 am »
dp(k) = max( dp(k+1) , k+dp(k+2) )
動態規劃,使用 d[MaxN] 記錄已求出的值不再遞迴
代碼: [選擇]
/*
NPSC 2014 國中組決 B. 半折植樹
dp(k) = max( dp(k+1) , k+dp(k+2) )
動態規劃,使用 d[MaxN] 記錄已求出的值不再遞迴
*/
#include <iostream>
//#include <cstdio>
#include <cmath>
#define MaxN 100
using namespace std;
int a[MaxN] , d[MaxN];
int n;
int dp( int k )
{
if( k>=n) return 0;
if( d[k]==0 )
{
d[k] = max( a[k]+dp(k+2) , dp(k+1) );
}
return d[k];
}
int main( )
{
t,i;
cin >>t;
while( t-- )
{
cin >> n;
for(i=0;i<n;++i) cin >> a[i];
for(i=0;i<n;++i) d[i]=0;
int ans=a[0];
ans += dp(2);
cout << ans << endl;
}   
   return 0;
}
/*
4
4
3 1 2 7
8
1 2 1 3 2 1 4 1
10
3 2 2 4 5 1 4 2 4 5
6
992 996 992 1000 996 994

-------------
10
8
19
2986
*/


39
NPSC2014國中組決賽 / NPSC 2014 國中組決 G. 卡恩買飲料
« 於: 一月 24, 2015, 01:26:34 am »
NPSC 2014 國中組決 G. 卡恩買飲料
s = 錢包中所有錢的總和 - 購買金額 p  , 留最少數量即是付最多
greedy 可, 但t有10^6,cin+cout應會逾時

代碼: [選擇]
/*
NPSC 2014 國中組決 G. 卡恩買飲料
s = 錢包中所有錢的總和 - 購買金額 p  , 留最少數量即是付最多
*/
#include <iostream>
#include <cstdio>
#include <cmath>
#define MaxN 7  // 錢幣種類
using namespace std;
int main( )
{
int v[7]={1,5,10,50,100,500,1000};
int c[7] ,  t,p,i;
scanf("%d",&t); //cin >>t;
while( t-- )
{
scanf("%d",&p); //cin >> p;
int s=0, n=0;  // 總金額、總數量
for(i=0; i<MaxN; ++i)
{
scanf("%d", &c[i]); //cin >>c[i];
s += ( c[i]*v[i] );
n += c[i];
}
s -= p;
for(i=MaxN-1; i>=0 && s>=0; --i)
{
if( s >= v[i] )
{
int d = min( s/v[i] , c[i] ); // v[i]面額可以留的數量
s -= ( d*v[i] );
c[i] -= d;
n -= d;
}
}
if( s > 0 ) printf("OAQ\n"); //cout << "OAQ" << endl;
else printf("%d\n",n); //cout << n << endl;
}   
   return 0;
}
/*
4
20 5 1 4 5 1 4 0
65 5 1 4 5 1 4 0
514 0 0 0 0 0 0 999
1000 1000 0 0 0 0 0 1
-------------
7
7
OAQ
1000
*/


40
NPSC2014高中組決賽 / NPSC 2014 高中組決 E. 鋼鐵旗幟競賽
« 於: 一月 23, 2015, 11:23:55 pm »
NPSC 2014 高中組決 E. 鋼鐵旗幟競賽
直接模擬: W時 A += (10+5*C)且C清空, L時B += 10且C+1但最多為5 , D時 A+=5、B+=5

代碼: [選擇]
/*
NPSC 2014 高中組決 E. 鋼鐵旗幟競賽
直接模擬: W時 A += (10+5*C)且C清空, L時B += 10且C+1但最多為5 , D時 A+=5、B+=5

*/
#include <iostream>
using namespace std;
int main( )
{
int t,n,i;
cin >>t;
while( t-- )
{
cin >> n;
int a=0,b=0,c=0;
char d;
for(i=1; i<=n; ++i)
{
cin >>d;
if( d == 'W' )
{
a += (10+5*c);
c=0;
}
else if( d == 'L' )
{
b += 10;
if(c<5) ++c;
}
else
{
a += 5;
b += 5;
}
}
cout << a << " " << b << endl;
}   
   return 0;
}
/*
3
5
WWWDW
5
WLLLD
10
WLLLLLLWLW
-------------
45 5
15 35
60 70
*/


頁: 1 [2] 3