100EDU祭

本文狀態：更新中

今天太晚，大致題意明天再補，這里先說做法，
本場是邊做java作業邊打的一場edu，臨近期末ddl的事情很多，

A. Dungeon

題目鏈接
做法：如果 a + b + c a+b+c a+b+c的和 s u m sum sum是9的倍數而且 m i n ( a , b , c ) ? 9 ≥ s u m min(a,b,c)*9 \geq sum min(a,b,c)?9≥sum就可以，原因是只有9的倍數才可能被蓄力炮同時秒掉， m i n ≥ s u m min \geq sum min≥sum是因為我們要保證前面的蓄力炮不能炸死其中的一個怪，否則就不滿足題意了.
代碼：

   int T;
   cin >> T;
   while(T--)
   {
      int a,b,c;
      cin >> a >> b >> c;
      int sum = a + b + c;
      if(sum % 9 == 0 && min(a,min(b,c))*9 >= sum)
      {
         cout << "YES" << endl;
      }
      else cout << "NO" << endl;
   }

B. Find The Array

題目鏈接
做法：我自己的方法是，對于給出的每一個數，我們輸出 ≤ a [ i ] \leq a[i] ≤a[i]的最大的那個2的倍數的數，比如一個數字是3，那么它的二進制是11，那么我們應該輸出二進制位10的數，即輸出2，此結論請讀者自己證明，
另外cf討論區找到了另外一種做法，而且附帶有證明，我覺得很好，貼在這里，
下面附上我的方法的代碼：

const int N = 55;
ll a[N];
 
ll calc(ll x)
{
   ll wei = 0,t = 1;
   while((t << wei) < x) ++wei;
   return max(1LL,(ll)pow(2,wei-1));
}
 
int main()
{
   int T;
   cin >> T;
   while(T--)
   {
      int n;
      cin >> n;
      rep(i,1,n) cin >> a[i];
      rep(i,1,n)
      {
         cout << calc(a[i]) << " ";
      }
      cout << endl;
   }
}

C. Busy Robot

題目鏈接
模擬，待補，

D. Pairs

題目鏈接
今天太晚，思路明天補，其實就是模擬范圍，
現附上代碼：

const int N = 1e6+6;
 
set<int> s1, s2;
int b[N], vis[N];
int n, ans1, ans2;
void init()
{
   ans1 = 0;
   ans2 = 0;
   cin >> n;
   MEM(vis, 0);
   rep(i, 1, n)
   {
      cin >> b[i];
      vis[b[i]] = 1;
   }
   s1.clear();
   s2.clear();
   rep(i, 1, 2 * n)
   {
      if (vis[i] == 0)
      {
         s1.insert(i);
         s2.insert(i);
      }
   }
}
int solve(int ans1, int ans2)
{
   rep(i, 1, n)
   {
      auto it1 = s1.lower_bound(b[i]);
      auto it2 = s2.lower_bound(b[i]); //找第一個小于b[i]的數
      if (it1 != s1.end())             //如果找到了
      {
         ans1++;
         s1.erase(it1);
      }
      if (it2 != s2.begin())
      {
         ans2++;
         it2--;
         s2.erase(it2);
      }
   }
   return abs(ans1 + ans2 - n) + 1;
}
 
int main()
{
   int T;
   cin >> T;
   while (T--)
   {
      init();
      cout << solve(ans1, ans2) << endl;
   }
   return 0;
}