NPSC補完計劃

登入註冊帳號.

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

最新消息:

歡迎光臨NPSC補完計劃

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

顯示文章

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

文章 - rscpp

頁: 1 2 [3]
41
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
*/


42
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
*/


43
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
*/


44
NPSC2014高中組決賽 / npsc 2014 高中決賽 C.北斗遺跡
« 於: 一月 23, 2015, 10:52:58 pm »
求K1 * K2 的所有因數的個數
因k1,k2<=10^6,建<=1000000的質數表
kk = k1*k1會大於 2^32,所以設為 long long
將 kk 化為質因數乘積: p1^n1 * p2^n2 .... pj^nj
則所有因數的個數為: (n1+1)*(n2+1) .... *(nj+1)

代碼: [選擇]
/*
NPSC 2014 高中組決 C. 北斗遺跡 , 求K1 * K2 的所有因數

類 ZJ:d756: 10290 - {Sum+=i++} to Reach N   N的奇數因數共有幾個? 且更簡單
*/
#include <iostream>
#include <cmath>
#define MaxN 1000000
using namespace std;
bool m[MaxN];
long long p[78500]; // 1000000 內的質數 78498個
int ps;
void genp() //建 <1000000的質數表
{
int i,j,k,q=int(sqrt(MaxN));
p[0]=2;
for(i=3; i<q; i+=2) // 只設定奇數
{
if(!m[i]) for(k=2*i, j=i*i; j<MaxN; j+=k ) m[j]=true;
}
for(ps=1, i=3; i<MaxN; i+=2 )
if(!m[i]) p[ps++] = i;
/* 印質數個數、前200
cout <<"tot:"<<ps<<endl;
for(j=0;j<200;++j)
{
cout <<p[j]<<" ";
if((j+1)%10==0) cout << endl;
}
*/
}
int main( )
{
   genp();
long long k1,k2,kk;
int cnt, i, t, ans,line=0;
cin >>t;
while( t-- )
{
cin >> k1 >> k2;
kk = k1*k2;
if(kk==1) cout << 1 << endl;
else
{
ans=1;
for(i=0;i<ps && kk!=1;++i)
{
for( cnt=1; kk%p[i]==0; ++cnt ) kk/=p[i];
ans *= cnt;
}
if( kk!=1 ) ans *= 2;
cout << ans << endl;
}
}   
   return 0;
}
/*
5
1 2
2 3
4 7
8 6
101 6
-------------
2
4
6
10
8
*/


45
NPSC2014國中組決賽 / Re: A 生日快樂喵
« 於: 一月 23, 2015, 12:26:06 pm »
這是我的程式碼
代碼: [選擇]
/*
  2014 國中組決賽 - 題目A 生日快樂喵
  若 n=0直接輸出0
  else while(n) >=9扣九且存入ans右方,否則n串至ans最前 {所以先輸出餘數}
 */
#include <iostream>
using namespace std;
int main()
{
  int t,n;
  cin >> t;
  while( t-- )
  {
    // string ans="";
     cin >> n;
     if(n==0) cout << 0 << endl;
     else
     {
         if(n%9)   cout << n%9 ;
         n/=9;
         for(int i=0; i<n; ++i) cout << 9;
         cout << endl;
     }       
  }
  return 0;
}

46
以金銀銅牌數排序1的名次存入s[0]
以總積分排序2的名次存入     s[1]
若s[0]>s[1]則 x+1、若s[0]<s[1]則 y+1
代碼: [選擇]
/* 2014國中組決賽 c 奧林希克運動會
輸.的第..有.個正整數T,代表測試資料的筆數。
每.筆測試資料的第..有.個正整數N,代表有在奧林希克運動會中得獎的城鎮數。接下來
有N .,每..都有三個.負整數gi; si; bi 分別代表各個城鎮的總.、銀、銅希克獎牌數。
‧ T <= 200
‧ 1 <= N <= 500
‧ 0 <= gi; si; bi <= 1000,且1 <= gi + si + bi <= 2000。
2
3
10 8 5
9 4 7
9 2 23
5
1 0 3
0 0 512
0 0 18
0 14 16
0 14 16
-------------
1 1
2 1
*/
#include <iostream>
#include <algorithm>
#define MaxN 1001
#define MaxN2 1002001
using namespace std;
typedef  struct dat
{
  int k;     // 城鎮序號
  int g,s,b; // 金銀銅牌數
  int m,p;  // m 以1001進位金銀銅數, p總積分*90 , *30 , *15
} st;
st a[500];

int s[2][500]; // 兩種排序的名次

bool cmp1(st x, st y)  // 依金銀銅牌數排
{
if(x.g != y.g) return x.g>y.g;
if(x.s != y.s) return x.s>y.s;
return x.b > y.b;
}
bool cmp2(st x, st y)  // 依積分排
{
return x.p > y.p;
}

int main()
{
  int t,n,i,j,k;
cin >> t;
   while( t-- )
   {
cin >> n;
      for( i=0; i<n; ++i)
{
      cin >> a[i].g >> a[i].s >> a[i].b;
a[i].m = a[i].g*MaxN2 + a[i].s*MaxN + a[i].b;
a[i].p = a[i].g*90 + a[i].s*30 + a[i].b*15;
a[i].k = i;
      }

int x,y=0;

sort(a,a+n , cmp1);
s[0][a[0].k] = y;
// for(i=0;i<n;++i) cout << a[i].k <<" : " << a[i].m << endl;

for(x=1; x<n; ++x)
{
if( a[x].m < a[x-1].m ) y=x;
s[0][a[x].k] = y;
}
sort(a,a+n , cmp2);
// for(i=0;i<n;++i) cout << a[i].k <<" : " << a[i].p << endl;
y=0;
s[1][a[0].k] = y;
for(x=1; x<n; ++x)
{
if( a[x].p < a[x-1].p ) y=x;
s[1][a[x].k] = y;
}
x=0;y=0;
for(i=0;i<n;++i)
{
if(s[0][i]>s[1][i]) ++x;
else if(s[0][i]<s[1][i]) ++y;
}
cout <<x<<" "<<y<< endl;
   }
  return 0;
}


47
NPSC2014高中組決賽 / 請問決賽題目在哪可找到
« 於: 十二月 08, 2014, 08:11:12 am »
以前不是都在活動日程中?
http://contest.cc.ntu.edu.tw/npsc2014/schedule.asp

48
NPSC2014國中組初賽 / NPSC-2014國中組初賽 D. 貓熊羽哲
« 於: 十一月 26, 2014, 12:13:59 am »
只有三步,各種方向 加轉90度只有15種,就不用寫旋轉,直接建表 {0右、1下、2左}

  [ 0] 、[1]、[2]、[3]、 [4]、[5]、[6]、 [7]、[8]、[9]、[10]、[11]、 [12]、[13]、[14]
  000、001、010、011、012、100、101、110、111、112、121、122、211、212、221
 
對每1格,各走以上15種,找最大值   {150x50x50x15x4應該不會逾時吧}
代碼: [選擇]
/*
NPSC 2014 國中組初賽 D.貓熊羽哲

*/

#include <cstdio>
//#include <iostream>
// using namespace std;
int a[50][50];
int mr[]={0 , 1, 0}; // 右、下、左
int mc[]={1 , 0,-1};

int b[15][3] = { {0,0,0}, {0,0,1}, {0,1,0}, {0,1,1}, {0,1,2} ,
{1,0,0}, {1,0,1}, {1,1,0}, {1,1,1}, {1,1,2} ,
{1,2,1}, {1,2,2}, {2,1,1}, {2,1,2}, {2,2,1} };
int main()
{
  int i,j,k,t,n,m ,ans;
  int r,c,d,sum;
  scanf("%d",&t);
    while( t-- )
    {
  scanf("%d %d",&n,&m);
      for(i=0; i<n; ++i)
      for(j=0; j<m; ++j)
scanf("%d", &a[i][j]);
ans = 0;
      for(i=0; i<n; ++i)
      {
      for(j=0; j<m; ++j)
      {
for(k=0;k<14;++k)
{
r=i; c=j;
sum=a[r][c];
d=0;
for(d=0; d<3; ++d)
{
r += mr[b[k][d]];  c += mc[b[k][d]];
if( r>=n || c<0 || c>=m) break;
sum += a[r][c];
}
if(sum>ans) ans=sum;
} // k
      } // j
      } // i
      printf("%d\n",ans);
   }
  return 0;
}
/*
3
3 4
6 1 1 1
9 5 1 1
2 2 7 1
5 5
8 8 1 1 1
1 8 8 1 1
1 1 2 1 1
2 3 1 7 7
5 4 1 9 7
10 10
706 534 580 290 302 775 15  761 815  710
46  415 863 791 374 962 872 57  950  365
525 768 54  593 469 299 623 648 264  280
830 825 590 987 911 227 696 981 244  534
107 1000 677 16 576 101 104 799 285  46
296 383 301 949 980 402 279 161 163  647
411 413 713 327 634 208 187 584 81   458
906 262 786 379 290 920 632 628 429  9998
562 695 914 835 23  544 917 431 678  2503
514 463 354 405 270 56  244 980 9161 391

------------
23
32
22340
*/


49
謝謝sagit老師,我看錯了,把 t 看成是x的範圍,
怎麼改呢?
兩數相乘的 10^9以內的各跑1次要多久?
三數相乘的 10^6 ,再試試吧!

50
NPSC2014高中組初賽 / NPSC2014-高中組初賽 B. 寧寧數貓咪
« 於: 十一月 25, 2014, 12:07:07 am »
這是二信高中哪組的原程式將 cin+cout改成scanf+printf的,聽說本來一直逾時,沒想到是這個問題,
如果早發現,第6題應該也可以過吧,可惜了!{ 恩齊、之芃、佑恩 }無法前進決賽,大學繼續努力了!
代碼: [選擇]
/*
npsc2014-高中組初賽 B. 寧寧數貓咪
 若讀1000筆左右 ,使用 cin、cout 約1秒、 scanf+printf約0.2秒
*/
#include<iostream>
#include <cstdio>
using namespace std;
int p[1001],r[1001];
int main(){
    int t , n;
    scanf("%d", &t);   // cin >> t;
    while(t--)
{
    scanf("%d", &n);  // cin >> n;
        for(int i=0;i<n;++i)
            scanf("%d %d", &p[i] , &r[i]);  // cin >> p[i] >> r[i];
        unsigned long int ans=r[0];
        int px = 1;
        bool over = false;
        for(int i=0;i<n-1 && !over ;++i)
{
px *= p[i];
            while( !(ans%p[i+1]==r[i+1]) )
{
                ans += px ;
                if(ans >= 955049953) over=true; 
            }   
        }
        if(over) printf("-1\n");  // cout << -1 << endl;
        else printf("%d\n",ans ); // cout << ans << endl;
    }
    return 0;
}
/*
5
2 3 1 5 4
3 5 1 7 1 11 1
10 2 0 3 2 5 4 7 5 11 1 13 1 17 1 19 1 23 1 29 1
[color=blue]168 2 1 3 1 5 3 7 4 11 0 13 0 17 0 19 0 23 0 29 0 31 0 37 33 41 12 43 1 47 36 53 23 59 20 61 37 67 61 71 56 73 5 79 72 83 78 89 31 97 78 101 13 103 66 107 53 109 19 113 56 127 47 131 86 137 74 139 135 149 34 151 19 157 113 163 27 167 166 173 166 179 107 181 14 191 102 193 68 197 60 199 198 211 20 223 48 227 117 229 186 233 195 239 217 241 211 251 224 257 174 263 169 269 154 271 154 277 212 281 79 283 231 293 45 307 276 311 53 313 252 317 278 331 96 337 41 347 118 349 285 353 334 359 99 367 348 373 238 379 273 383 4 389 104 397 154 401 283 409 188 419 208 421 86 431 70 433 39 439 185 443 429 449 13 457 385 461 402 463 407 467 395 479 114 487 97 491 452 499 380 503 332 509 19 521 164 523 176 541 472 547 534 557 486 563 399 569 523 571 492 577 130 587 366 593 326 599 160 601 252 607 402 613 244 617 589 619 424 631 534 641 336 643 124 647 313 653 232 659 134 661 137 673 364 677 637 683 125 691 196 701 543 709 11 719 96 727 231 733 64 739 347 743 725 751 249 757 585 761 280 769 400 773 723 787 269 797 71 809 374 811 133 821 357 823 426 827 581 829 503 839 312 853 445 857 583 859 9 863 647 877 461 881 141 883 685 887 200 907 721 911 370 919 340 929 793 937 522 941 823 947 453 953 50 967 139 971 570 977 212 983 575 991 460 997 722 [/color]
168 2 0 3 0 5 2 7 3 11 10 13 12 17 16 19 18 23 22 29 28 31 30 37 32 41 11 43 0 47 35 53 22 59 19 61 36 67 60 71 55 73 4 79 71 83 77 89 30 97 77 101 12 103 65 107 52 109 18 113 55 127 46 131 85 137 73 139 134 149 33 151 18 157 112 163 26 167 165 173 165 179 106 181 13 191 101 193 67 197 59 199 197 211 19 223 47 227 116 229 185 233 194 239 216 241 210 251 223 257 173 263 168 269 153 271 153 277 211 281 78 283 230 293 44 307 275 311 52 313 251 317 277 331 95 337 40 347 117 349 284 353 333 359 98 367 347 373 237 379 272 383 3 389 103 397 153 401 282 409 187 419 207 421 85 431 69 433 38 439 184 443 428 449 12 457 384 461 401 463 406 467 394 479 113 487 96 491 451 499 379 503 331 509 18 521 163 523 175 541 471 547 533 557 485 563 398 569 522 571 491 577 129 587 365 593 325 599 159 601 251 607 401 613 243 617 588 619 423 631 533 641 335 643 123 647 312 653 231 659 133 661 136 673 363 677 636 683 124 691 195 701 542 709 10 719 95 727 230 733 63 739 346 743 724 751 248 757 584 761 279 769 399 773 722 787 268 797 70 809 373 811 132 821 356 823 425 827 580 829 502 839 311 853 444 857 582 859 8 863 646 877 460 881 140 883 684 887 199 907 720 911 369 919 339 929 792 937 521 941 822 947 452 953 49 967 138 971 569 977 211 983 574 991 459 997 721

--------------- out
4
1
-1
-1
955049952
*/

51
這是來亂的,大家抱歉了!「數大就是{沒}
因題目沒看清,這個邏輯不通。

我的想法是先建表,然後再查對每組查詢的左值lv及右值rv定出其在表中的位置,即可得出數量

雙迴圈 i=1~10000, j=i+1~ i+49 建立連續數的乘積表{<=1e18 才存} set <LL > s
  將s轉至表中vector<LL > v 數字由小至大排序且不重複,
對每組查詢 lv , rv 找出 v[a]>=lv 且最接近的索引 a 、 v[ b] <= rv 且最接近的索引 b

先拋磚引玉,請高手指正,大家一起來補完。
代碼: [選擇]
/*
npsc 2014-高中組初賽 題目 D 小小郭的密碼

*/
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <set>
#define LL unsigned long long int
using namespace std;
set < LL > s;
set < LL >::iterator is;
vector < LL > v;

int bsrch(LL key , int u)  //二分搜找 v[m]<=key的 m
{
int l=0 , r=u  ;
int m = (l+r)/2 ;
while( v[m] != key && l<=r )
{
  if(v[m]>key) r = m-1;
  else l=m+1;
  m = (l+r)/2;
}
return m;
}

int main()
{

  int i,j,k,n,r,cnt=0;
  // 建表
    s.insert(0);
  for(i=1;i<=10000;++i)
  {
  LL  p=i;
  k=i+50; // 10^18 < 2^60 < 49!
    for(j=i+1; j<k && p < 10e18 ; ++j)
    {
if( (p>10e17 && j >10) || (p>10e16 && j>100) || (p>10e15 && j>1000) ) break;
p *= j;
if( p<=10e18) s.insert(p);
}
}
// 將 set 依序存入 vector
for(is=s.begin(); is!=s.end(); ++is) v.push_back(*is);

int u=v.size()-1;
// cout <<v.size() << "個," << v[0]<< "," << v[1]<< "," << v[u] << endl;
// for(i=0;i<=100;++i) { cout <<v[i]<<" "; if((i+1)%5==0) cout << endl; }
// 讀 lv rv 後,以二分搜定左右索引值

LL lv,rv;
int t , a , b;
cin >> t;
while(t--)
{
cin >>lv >> rv;
a = bsrch( lv , u );
if(v[a]!=lv) ++a;
b = bsrch( rv , u );
// cout << lv << ":" << v[a] << " ~ ";
// cout << v[b] << ":" << rv << endl;
if(b<a) cout << 0 << endl;
else cout << b-a+1 << endl;
}
  return 0;
}
/*
8
1 10
5 30
6 131
7 10
12 12
2 720
3 6333
10000 10000000000
--------
2
5
12
0
1
33
99
12521

*/

52
NPSC2014高中組初賽 / Re: NPSC2014-高中組初賽A. 禹鍺的鞋櫃
« 於: 十一月 23, 2014, 11:00:47 am »
謝謝指正,好像是我搞不清楚題意!

給最小的 k ,讓禹鍺挑任意 k 雙皆「需」符合,我有一個方向如下,
不曉得邏輯對不對、會不會超時?

先找LCS {若不找直接 1~n 二分切?}
再由x=1~lcs各試 { <- 二分切 }
 C(n,x)個組合皆可才行,找x=i可過,但x=(i+1) 不過的 x

53
NPSC2014高中組初賽 / NPSC2014-高中組初賽A. 禹鍺的鞋櫃
« 於: 十一月 22, 2014, 10:51:30 pm »
應該是 LCS 吧, N-LCS,但是
題目的範例中第二組資料
3 1 2
2 3 1
各捐2(捐一個k=1) 之後不是剩 3 1 嗎,為何給的解 k 是 2 ?

雖然可能我誤解題意,但既然解了,就 pose 一下程式碼吧!
懇請高手指正,先謝了!
代碼: [選擇]
/*
 NPSC2014-高中組 A. 禹鍺的鞋櫃
 不曉得是不是我誤解題意, 第2組: 3 1 2 捐2後剩 3 1
*/
#include<iostream> //max
#include<cstring> //memset
using namespace std;
int a[1000],b[100000];
int dp[2][100001];

int main()
{

    int t , n , m , i, j, k ;
    cin >> t;
    while( t--)
    {
cin >> n >> m;
for(i=0;i<n;++i) cin >> a[i];
for(j=0;j<m;++j) cin >> b[j];
      memset(dp,0,sizeof(dp));
      for(i=0,k=0; i<n; ++i,k=1-k)
        for(j=0; j<m; ++j)
           {
              if(a[i]==b[j])
      dp[1-k][j+1]=dp[k][j]+1;
  else
  dp[1-k][j+1]=max( dp[1-k][j], dp[k][j+1] );          
           }
   cout << n- dp[n%2][m] << endl;     
    }
    return 0;
}

/*
4
3 5
1 1 2
1 3 4 2 1
3 3
3 1 2
2 3 1
4 3
1 2 1 2
4 5 4
2 2
1 2
2 1
-----------我的out
1
1  {3 1 2}捐1個 2 剩 3 1
4
1
但範例out是
1
2
4
1

*/

54
NPSC2014高中組初賽 / NPSC-2014高中初賽F 校園偶像計劃
« 於: 十一月 22, 2014, 08:03:12 pm »
我的想法是建struct xxx { int u; double spc[3], tot } r[25];
計算每一位社員對所有曲目的得分累計至 tot內,
然後 sort(r,r+n, cmp) , cmp自訂依tot由大至小排序
取前9位的tot平均,將此九位的學號依學號由小至大列出
{ 本解題方向由二信高中簡佑恩提供意見 }
代碼: [選擇]
/*
npsc 2014初賽-高中組-F:校園偶像計劃

*/
#include <iostream>
#include <iomanip>
#include <set>
using namespace std;
struct mb {
int u;
double spc[3], tot;
} r[25];
bool cmp(mb x , mb y )
{
if(x.tot>y.tot) return true;
return false;
}
int main()
{
    int t,n,m , i,j,k;
    char a , y ; // 逗號 , 歌曲類
    cin >> t;
    while(t--)
    {
  cin >> n >> a >> m;
  for(i=0; i<n; ++i)
  {
cin >> r[i].u >> a >> r[i].spc[0] >> a
    >> r[i].spc[1] >> a >> r[i].spc[2];
r[i].tot = 0;
}
for(j=0; j<m ; ++j)
{
if(j) cin >> a;
cin >> y;
if ( y=='s' ) k=0;
else if ( y=='p' ) k=1;
else k=2;
  for(i=0; i<n; ++i)
  {
r[i].tot += r[i].spc[k];
}
}
sort ( r , r+n , cmp );
set <int> uo;
set <int>::iterator is;
double sum=0;
for( i=0; i<9; ++i )  // 前九位的總分、將學號加入 set
{
   uo.insert(r[i].u);
   sum += r[i].tot;
}
  cout << fixed << setprecision(3) << sum / 9 << endl;
  is=uo.begin(); cout << (*is) ;
  for(++is; is!=uo.end(); ++is) cout << "," << (*is) ;
  cout << endl;
   }
  return 0;
}
/*
2
10,3
1,2000.000,5000.000,3000.000
2,4000.000,2000.000,2000.000
3,1000.000,5000.000,3000.000
4,3000.000,2000.000,3000.000
5,2000.000,1000.000,5000.000
6,1000.000,3000.000,1000.000
7,1000.000,5000.000,3000.000
8,5000.000,3000.000,5000.000
9,4000.000,4000.000,4000.000
10,5000.000,1000.000,2000.000
s,p,c
12,5
1,796.501,13.025,994.582
2,676.916,409.636,561.610
3,848.811,443.469,586.526
4,221.629,653.935,608.985
5,589.992,555.418,413.737
6,539.929,334.949,46.011
7,547.726,103.542,559.104
8,934.054,673.369,373.407
9,860.740,995.345,3.964
10,553.694,620.526,438.781
11,48.880,503.052,638.534
12,213.942,398.149,963.539
s,p,s,c,c
-----------------------
9444.444
1,2,3,4,5,7,8,9,10
2894.192
1,2,3,5,7,8,9,10,12
*/


55
NPSC2014國中組初賽 / NPSC-2014-國中組A.棒球中的統計學
« 於: 十一月 22, 2014, 05:08:42 pm »
/*
npsc 2014初賽-國中組-A:棒球中的統計學
以下程式邏輯大概可以吧?!
*/
代碼: [選擇]
#include <iostream>
#include <iomanip>

using namespace std;


int main()
{
  int n,a,h,b,p,t,s;
  double ops;
cin >> n;
   while(n--)
   {
  cin >> a >> h >> b >> p >> t >> s;
  ops = double(h+b+p) / (a+b+s+p) + double(t) / a;
  cout << fixed << setprecision(3) << ops << endl;
   }
  return 0;
}
/*
3
539 155 94 3 299 2
644 181 19 12 302 7
561 188 70 4 317 6
------------
0.950
0.780
0.974
*/

56
NPSC2014國中組初賽 / NPSC-2014 國中組初賽 C. 新.3N+1
« 於: 十一月 22, 2014, 05:00:02 pm »
我覺得應該可以這麼解吧!?
2^0~2^30建表
找到 Ans = 2^x >= N 且最接近 N 的 Ans , A一定是1 ,B = Ans-N ,
但Ans=2^x 的話直接輸出 1 1
x<=30 ,循序搜、二分搜皆可吧?
代碼: [選擇]
/*
npsc 2014初賽-國中組-C:新.3N+1
*/
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
  int t,n,i,x=1, p[31];
  int l,u,m,a,b;
  for(i=0; i<31; ++i, x*=2) p[i]= x; //  cout << "2^"<<i << " " << p[i] << endl;
  scanf("%d", &t);
while(t--)
  {
  scanf("%d", &n);
  l=0; u=30; m=(l+u)/2;
  while( l<=u && p[m]!=n )
  {
if(n>p[m]) l=m+1;
else u=m-1;
m=(l+u)/2;
}
if(n==p[m]) printf("1 1\n");
else printf("1 %d\n",p[m+1]-n);
}
  return 0;
}
/*
10
4
5
32
127
257
1022
2050
65555
9876543
999999999
--------------
1 1
1 3
1 1
1 1
1 255
1 2
1 2046
1 65517
1 6900673
1 73741825
*/

57
/* NPSC 2009 國中組決賽 pF.風鈴  [C++] 遞迴解
   我自己覺得,以下的程式用遞迴解,應該比較容易理解
 
isb() 傳回風鈴的值 若 (開頭,可遞迴 左風鈴,右風鈴 )右括號
                         若開頭不是 ( 而是數字, 取出該數值 傳回


*/
代碼: [選擇]
#include <iostream>
#include<cstring>
using namespace std;

string s;   //讀入的字串
int p;      // 處理至哪一字元 s的索引值

int isb()   //不平衡的傳回 -1 ,有平衡的傳回其 值
{
   char c=s[p];
   if( c=='(' )  // 左括號
   {
      ++p;
      //遞迴
      int n1=isb();   //左值
      if( n1 < 0 ) return -1;
      if( s[p] == ',' ) ++p;   // ,
      int n2=isb();   //右值
      if( s[p]==')' ) ++p;   // 右括號 )
      if( n2 < 0 || n1 != n2 ) return -1;
      else return (n1+n2);
   }
   else // 數字
   {
      int v1=s[p]-48; ++p;
      while( s[p] != ',' && s[p]!=')' )
      {
         v1=v1*10+s[p]-48;
         ++p;
      }
      return v1;
   }
}

int main( )
{
   int n;
   cin >> n;
   while( n-- )
   {
      p=0; // 字串 s 的索引值,從0開始     
      cin >> s;
      int num = isb();
      if ( num < 0 ) cout << "No" <<endl;
      else cout <<"Yes" << endl;
   }
    return 0 ;
}

58
NPSC2009國中組決賽 / Re: [解法]B. KjumpingCube {遞迴解}
« 於: 八月 31, 2014, 12:53:04 pm »
/* 我有使用遞迴的方法
假設遞迴函式 bool pu (p綠或藍 , i列號 , j 行號)  // 玩家 p 在(i,j)加一珠,若可取勝 true
程式碼如下
*/

代碼: [選擇]
#include <iostream>
#include <cstring>
using namespace std;
int cv[12][12] , cp[12][12] , ne[12][12] , cnt[3];
// [color=blue]cv珠數 、 cp 誰擁有、 ne 相鄰格數 、 cnt [1],cnt[2]兩玩家地盤數[/color]
int rxc;
bool pu( int p , int i , int j)
{
   if( cp[i][j] != p)
   {
          ++ cnt[p];  //原不屬於 p , 計數+1
         if( cp[i][j]!=0 ) -- cnt[3-p];  //原屬於對手 , 對手-1
   }
   cp[i][j] = p;     // 屬於 p
   ++ cv[i][j];
   if( cnt[p] == rxc ) return true;  //已全佔{win}
   if( cv[i][j] <= ne[i][j] ) return false; // 未滿
// 本格滿了,分至四鄰
   cv[i][j] = 1;
   if( cv[i-1][j] ) if( pu(p,i-1,j) ) return true;
   if( cv[i+1][j] ) if( pu(p,i+1,j) ) return true;
   if( cv[i][j-1] ) if( pu(p,i,j-1) ) return true;
   if( cv[i][j+1] ) if( pu(p,i,j+1) ) return true;
   return false;
}
main()
{
   int  r , c , t , i , j , k , n , p;
   string ostr[3]={"processing","GREEN","BLUE"};
   while (cin >> r >> c >> t , (r || c || t) )  // 多組 0 0 0 結束
   {
// init
      memset(cv,0,sizeof(cv));
      memset(cp,0,sizeof(cp));
      cnt[1]=0 ; cnt[2]=0;
      rxc = r*c;
      for(i=1; i<=r; ++i)
         for(j=1; j<=c; ++j)
            cv[i][j]=1;
      for(i=1; i<=r; ++i)
         for(j=1; j<=c; ++j)
            ne[i][j] = cv[i-1][j] + cv[i+1][j] + cv[i][j-1] + cv[i][j+1] ;
// t 個回合
      bool ret;
      for(p=1,k=0; k<t; ++k)
      {
         cin >> i >> j;
         ret=pu(p,i,j);
         if ( ret ) break;
         p=3-p;        // 玩家 p{1,2}
      }
      if( k==t) p=0;   //未分勝負
      else while(k+1<t) {cin >> i >> j; ++k; }  [color=limegreen]//提前分勝負,未讀完的讀完[/color]
      cout << cnt[1] << " " << cnt[2] << " " << ostr[p] << endl;
   }     
   return 0;
}

59
NPSC2009國中組決賽 / C.跑跑卡丁車{C++加STL}
« 於: 八月 31, 2014, 12:42:37 pm »
/*
我第一次使用,不知道如何貼程式碼!,有人可以給個指導嗎?
解這題時,有點偷懶想看一下參考,沒找到,解完後就想補完一下


gj:g061 / zj:b255   g061: C.跑跑卡丁車關鍵字: NPSC 2009 國中組決賽
讀入的每筆資料 { 索引 i , 名字 s , 時間串 t }   
因為輸入的的時間串 "hh:mm:ss.xxx" 扣掉冒號及小數點,最多 hhmmssxxx最多9位數
將 t 轉成整數 tnum 的方法應可以各顯神通, tnum加上索引i建結構 nt ,
以 vector< nt > vt 存 {i,tnum} , 以 陣列或 vector<string>vs 存對應的名字
將 vt 以自訂比較函式 cmp 來做 sort ,需注意若 tnum相同, 依 i 的順序排
接著,記住前1/3的最後一個在vt的索引k ,然後取出前 1/3 將其在vs的索引值i放入 set<int>out
輸出(1) 依序將 out 內的索引值取出對應vs的名字印出,
    (2) 再印出vt[k]之後 tnum值與vt[k]的tnum值相同的名字

*/
代碼: [選擇]
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
typedef struct ns { int t,i; } nt;
nt nts;
vector <nt> vt;
vector <string> vs;
bool cmp( nt a , nt b )
{
   if(a.t<b.t) return true;
   if(a.t>b.t) return false;
   return ( a.i < b.i );
}
int main( )
{
   int  i , j,  tnum , n;
   string s,t;
 
   while ( cin >> n , n )
   {
      vs.clear();  vt.clear();
      for(i=0; i<n; ++i)
      {                    //每筆資料 s名字、 t時間串
         cin >> s >> t;
         vs.push_back(s);
         int tlen = t.size();
         tnum = (t[0]-48)*100000+(t[1]-48)*10000 + (t[3]-48)*1000+(t[4]-48)*100 + (t[6]-48)*10+t[7]-48;
         for(j=9; j<12; ++j) tnum = tnum*10 + (j>tlen ? 0 : t[j]-48 );
         nts.t=tnum; nts.i=i;
         vt.push_back(nts);
      }
      sort(vt.begin(), vt.end(),  cmp );  // 排序,以自訂比較函式 cmp
      cout <<"LIST START" <<endl;
      int k=n/3;
      // set<out> 存入 前1/3 {依原輸入序} ; 再依序印出
      set <int> out; 
      set <int>::iterator it;
      for(i=0; i<k; ++i) out.insert(vt[i].i);
      for(it=out.begin(); it != out.end() ; ++it ) cout <<  vs[ (*it) ]  <<endl;
// 補印所有與 最後入圍者 有相同 tnum 者
      i=k-1;
      while( i<n-1 && vt[i].t == vt[i+1].t  )
      {         
         ++i;  cout <<  vs[vt[i].i]  <<endl;
      }
      cout <<"LIST END" <<endl;
   }
   return 0 ;
}

60
綜合討論區 / Re: 給新手的程式設計學習參考
« 於: 八月 26, 2014, 04:56:08 pm »
sagit老師太棒了,今年才知道有這個好所在
另 green judge 也很棒,初、中程式 學習 C++ 的最佳網站
我想按讚,數量就一個int吧 2^32-1

頁: 1 2 [3]