NPSC補完計劃

登入註冊帳號.

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

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃
 最新文章
頁: [1] 2 3 ... 10
 1 
 於: 十二月 11, 2019, 05:44:40 pm 
作者 089487 - 最新文章 由 089487
#include<bits/stdc++.h>
using namespace std;
int main()
{
   queue<char> q;
   int n,m;
   cin>>n>>m;
   string s;
   cin>>s;
   //cout<<s<<"\n";
   for(int i=0;i<s.length();i++) q.push(s);
   int x[m][4];
   string y[m][4];
   for(int i=0;i<m;i++)
   {
      for(int j=0;j<4;j++) cin>>x[j];
      for(int j=0;j<4;j++) cin>>y[j];
   }
   char c[4]={'N','P','S','C'};
   int r2=0;
   //cout<<r2<<"r";
   //system("pause");
   while(s.length()<n)
   {
      //cout<<s<<" ";
      //cout<<q.front();
      int mood=find(c,c+4,q.front())-c;
   //   cout<<"mood"<<mood<<"\n";
      for(int i=0;i<y[r2][mood].size();i++)
      {
         q.push(y[r2][mood]);
         //s2+=i;
      }
      s+=y[r2][mood];
      r2=x[r2][mood]-1;
      q.pop();
   }
   for(int i=0;i<n;i++) cout<<s;
   cout<<"\n";
}

 2 
 於: 十二月 11, 2019, 05:43:41 pm 
作者 089487 - 最新文章 由 089487
#include<bits/stdc++.h>
using namespace std;
uint64_t hasha(char *s);
int main()
{
   char s[1000001];
   cin>>s;
   uint64_t k=hasha(s);
   cout<<k<<"\n";
}
uint64_t hasha(char *s)
{
   uint64_t meow=7122ul;
   while(*s!=0)
   {
      meow=(meow<<13) ^ (meow>>11) ^ (meow<<9) ^ (meow>>7) ^ (meow<<5) ^ (meow>>3) ^(meow<<1) ^((uint64_t)(*s++) * 0xdeadbeeful);
   }
   return meow;
}

 3 
 於: 十二月 11, 2019, 05:43:07 pm 
作者 089487 - 最新文章 由 089487
#include<bits/stdc++.h>
using namespace std;
int main()
{
   int n,k,p;
   cin>>n>>k>>p;
   int plate[n];
   int people[n];
   int p2[k];
   int h[p];
   for(int i=0;i<n;i++)
   {
      cin>>plate;
      if(i<k) p2=plate;
    }
   for(int i=0;i<n;i++)
   {
      cin>>people;
      if(i<p) h=people;
   }
   int x=p+1;
   int y=k+1;

   while(y<n&&x<n)
   {
   //      for(auto j:p2) cout<<j<<" ";
   //   cout<<"\n";
   //   for(auto j:h) cout<<j<<" ";
   //   cout<<"\n";
      bool f=0;
      for(int j=0;j<k;j++)
      {
         int r2=find(h,h+p,p2[j])-h;
         if(r2!=p)
         {
            f=1;
            p2[j]=plate[y];
            h[r2]=people
  • ;

            x++;
            y++;
         }
         if(x>=n||y>=n) break;
      }
      if(!f){
         cout<<"No\n";return 0;
      }
   }
   cout<<"Yes\n";
}

 4 
 於: 十二月 08, 2019, 07:00:08 pm 
作者 lose - 最新文章 由 lose
原文網址: https://www.facebook.com/permalink.php?story_fbid=431563037518690&id=338441636830831

引用
NPSC題解
先講下,我是拉基我只有一題,寫這題解是聽裁判寫出來的,只是因為想找去年題解找不到覺得很不爽,才幫別人紀錄一下,拜託電神別嘴,等等邊聽邊更新。

pA 逆序輸出
題:給一正整數及24格儲存整數的格子,構造一指令印出從N ~ 0的數字,指令有將任意格複製到另一格,任一格 +1,輸出第x格,要求兩次輸出中不得超過15個指令。
使用log2(N)個格子,分別儲存lowbit為(1 << i)(i <= log2(N))的值,每次取小於且最接近需要的值的格子複製過來,在暴力加到需要的值,證明感覺很麻煩,不過應該可以感覺的到,每次操作都不會太多。

pB 忙碌的國度
題:一二維座標平面存在兩種點,一種代表公司並包含該公司下班時間,另一種代表餐廳並包含打烊時間及美味程度。問對於每一間公司,可以在下班後並在打烊前到達的餐廳的美味程度最大值為和?
formula : (Off work time + abs(x2 - x1) + abs(y2 - y1) <= Closure)
這題留言裡有超級電神的解釋,去膜拜吧。

pC 最小三倍完全數
題:求最小N倍完全數(N >= 1 && N <= 5)
這題我坐在那思考著自己跟垃圾有什麼差別時聽到了許多的解法,評審的解法也感覺很酷,但是,\爆搜!!/。

pD 回文樹
題:給一字串,將其排成字典序最小的回文字串。
引用評審的一句話:就排阿。

pE 密碼鎖
題:給N, K,及一N數字排列,問有幾種排列在移動K次後會剛好等於該排列。
首先應該很快的可以想到,不管排列長什麼樣子,結果都一樣,也就是答案只跟N, K有關,再來好像可以位元DP,這題我聽題解時在恍神,所以還要再推一下,之後更新。

pF 猜數字
題:互動題,給k個數字n,做最少次詢問得到每一個數字,每次詢問回傳是否大於詢問。
首先定義一函數F(N, K) 表示K個數字N大小區間的最佳詢問,就這樣去做分治。
這題其實我也沒有搞很懂為甚麼是那一坨東西,坐等電神解釋。
那一坨東西:F(N, K) = ( (N - 1) mod 2 * ceil( log2 ( (N - 1) / 2K + 1 ) ) ) + 1
我不會打很酷的數學符號QQ

pG 航線建設
題:給N, Q代表對於N個節點的圖有K次操作,每次操作可以加上一條邊或刪除一條邊,對於每次操作輸出當前MST的直徑,若不連通則輸出-1。
這題評審講了兩個解法,不過第一個解法我完全聽不懂,所以就講第二種。
記得沒錯的話就是很簡單的暴力,每次操作就用並查及維護及確認是否連通,做出最小生成樹,並找直徑。應該沒有這麼簡單拉,不過我有點忘了。

pH 鐵路維修問題
題 : 給N個節點及N - 1條邊,求任兩點間距離乘上路上最大邊權的和。

這題評審給了3個做法,第二個我不是很會用treap,第三個我直接問號
,所以就講第一個就好。

首先要先想辦法用O(n)的時間求出每一個點到任意點的邊數,方便後續查詢。可以先從任意點開始DFS,使用簡易dp求出對於每個節點的所有子節點到該節點的邊數和。接下來再做一次DFS,這時我們已經有了每個節點的下面的邊數和,所以就剩下上面的。而上面的我們可以再用祖先的狀態推過來,對於每個節點,他上面的邊數和會是祖先除了自己以外所有的邊數和加上祖先自己上面的邊數和,這樣就可以求出對於任意點的邊數和了。

再來整題就變簡單了。因為是乘上最大的邊,所以我們可以對於所有的邊,去算出以這條邊為最大的邊的答案。直接依照邊權去由小排到大,當增到第i個邊權時,代表目前圖中最大的邊權就會是i這條邊,所以就用目前的圖去算出答案,一直到把全部的邊都加進去。

最近粉專突然被一堆電神看到,有點緊張。感覺內容有超級多的錯誤,如果電神們看到有問題,請不要吝嗇直接辱罵並糾正我吧。

 5 
 於: 十二月 08, 2019, 04:53:27 pm 
作者 lose - 最新文章 由 lose
題目要求:可分割價值的物品,一旦要分割有額外的花費

參考概念:
轉換成數形幾何去思考,X 軸為重量,Y 軸為價值,我們會得到一個 X、Y 嚴格遞增的單調曲線。若我們從前 i 個物品的曲線推到前 i+1 個物品的曲線,可以知道是兩個曲線的最大值,而放入這第 i+1 個物品的曲線是前一個曲線配上 Minkowski Sum 的結果。只看這一個物品的曲線,也是一個單調遞增的曲線。

仔細推敲兩個合併的結果,可以發現不論怎麼取最大值、疊合曲線,每一個曲線上的線段都恰好對應到一個物品的分割或不分割。因此最佳解至多有一個物品被分割。那麼窮舉會分割的物品,時間複雜度落於 O(n^2 m)。

離上一次參與已離七年有餘,礙於沒地方測試,可能會 TLE 的代碼如下

代碼: [選擇]
#include <bits/stdc++.h>
using namespace std;

struct Item {
int w, v, c;
bool operator<(const Item &o) const {
return w < o.w;
}
};

int main() {
int n;
int m;
Item items[2005];
while (scanf("%d %d", &n, &m) == 2) {
for (int i = 1; i <= n; i++)
assert(scanf("%d %d %d", &items[i].w, &items[i].v, &items[i].c) == 3);

double ans = 0;
static int dpBase[2005][10005] = {};
for (int j = 1; j <= n; j++) {
int w = items[j].w;
int v = items[j].v;
for (int k = 0; k <= m; k++) {
dpBase[j][k] = dpBase[j-1][k];
if (k >= w)
dpBase[j][k] = max(dpBase[j][k], dpBase[j-1][k-w] + v);
}
}
for (int i = 0; i <= m; i++)
ans = max(ans, (double) dpBase[n][i]);
for (int i = 1; i <= n; i++) {
if (items[i].v <= items[i].c)
continue;
static int dp[10005];
memcpy(dp, dpBase[i-1], sizeof(dp[0])*(m+1));
for (int j = i+1; j <= n; j++) {
int w = items[j].w;
int v = items[j].v;
for (int k = m; k >= w; k--)
dp[k] = max(dp[k], dp[k-w] + v);
int same = memcmp(dp, dpBase[j], sizeof(dp[0])*(m+1));
if (same == 0) {
memcpy(dp, dpBase[n], sizeof(dp[0])*(m+1));
break;
}
}

for (int j = 0; j <= m; j++) {
double val = dp[j];
if (m-j >= items[i].w) {
val += items[i].v;
} else {
double cwv = (double) (m-j) / items[i].w * items[i].v - items[i].c;
if (cwv > 0)
val += cwv;
}
ans = max(ans, val);
}
}
printf("%.20lf\n", ans);
}
return 0;
}

 6 
 於: 十一月 23, 2019, 11:49:31 am 
作者 LY02 - 最新文章 由 sagit
請問
#define endl '\n'
這一列是不是可以省略?
直接寫
cout<<'\n';
是可以的嗎?

可以

 7 
 於: 十一月 22, 2019, 08:22:22 pm 
作者 Felicity - 最新文章 由 Felicity
這題只需要判斷每個垃圾大小是否一樣
如有錯誤,麻煩指正,謝謝
引用
#include<cstdio>
int main()
{
   int i,n,a,b,f=1;
   scanf("%d %d",&n,&a);
   for(i=1;i<n;i++)
   {
      scanf("%d",&b);
      if(a!=b)
         f=0;
   }
   if(f)
      printf("Yes\n");
   else
      printf("No\n");
   return 0;
}

 8 
 於: 十一月 22, 2019, 08:15:24 pm 
作者 Felicity - 最新文章 由 Felicity
這題分成兩個情況做:一個是Y上W下,一個W上Y下(上下是指輸入順序)
如有誤,麻煩指出,謝謝
引用
#include<cstdlib>
#include<cstdio>
#include<cstring>
char sa[20001],sb[20001];
int main()
{
   scanf("%s %s",sa,sb);
   int i,y=0,yy=0,ww=0,w=0,wa=0,wb=0,ans=0;
   for(i=0;i<strlen(sa);i++)
   {
      if(sa=='Y')
      {
         wa+=i-y;
         y++;
      }
      else
      {
         wb+=i-w;
         w++;
      }
   }
   for(i=0;i<strlen(sb);i++)
   {
      if(sb=='W')
      {
         wa+=i+y-ww;
         ww++;
      }
      else
      {
         wb+=i+w-yy;
         yy++;
      }
   }
   ans=(wa>wb?wb:wa);
   y=0,yy=0,ww=0,w=0,wa=0,wb=0;
   for(i=0;i<strlen(sb);i++)
   {
      if(sb=='Y')
      {
         wa+=i-y;
         y++;
      }
      else
      {
         wb+=i-w;
         w++;
      }
   }
   for(i=0;i<strlen(sa);i++)
   {
      if(sa=='W')
      {
         wa+=i+y-ww;
         ww++;
      }
      else
      {
         wb+=i+w-yy;
         yy++;
      }
   }
   if(wa<ans)
      ans=wa;
   if(wb<ans)
      ans=wb;
   printf("%d\n",ans);
   return 0;
 }

 9 
 於: 十一月 22, 2019, 08:03:15 pm 
作者 LY02 - 最新文章 由 Felicity
請問
#define endl '\n'
這一列是不是可以省略?
直接寫
cout<<'\n';
是可以的嗎?

 10 
 於: 十一月 17, 2019, 10:40:01 pm 
作者 LY02 - 最新文章 由 sagit
這個網站是不是都沒人了阿

站長還活著,但沒什麼人會來了
曾經有一度這網站被NPSC官方網站列入參考資料的網站,
後來一次改版之後就被拿掉了,
然後人就越來越少了。

頁: [1] 2 3 ... 10