题目链接：

A. Game Shopping 题目：

题意：有n件物品，你又m个钱包，每件物品的价格为ai，每个钱包里的前为bi。你站在第一件物品前，如果你的第一个钱包能购买这件物品，你第一个钱包的钱直接消失（就相当于你是用第一个钱包里的所有钱购买了这件物品，不会找钱），如果无法购买那么就跳到下一件物品，以此类推，问你总共能购买多少件物品。

思路：直接模拟即可。

代码如下：

1 #include 
      
        2 using namespace std; 3  4 const int maxn = 1007; 5 int n, m, ans; 6 int a[maxn], b[maxn]; 7  8 int main() { 9     cin >>n >>m;10     for(int i = 0; i < n; i++) {11         cin >>a[i];12     }13     for(int i = 0; i < m; i++) {14         cin >>b[i];15     }16     for(int i = 0, j = 0; i < n ; i++) {17         if(j >= m) break;18         if(b[j] >= a[i]) {19             j++;20             ans++;21         }22     }23     cout <
       
        <
       
      

 

B. Minimum Ternary String  题目：

题意：给你一个只含012的串，0可以和1交换，1可以和2交换，0不可以和2交换，问进行多次交换后字典序最小的串是啥。

思路：因为1可以和02交换，所以要想字典序最小1必须全在2前面；2不能和0换，所以2和0的相对位置不变。故此题的思路就是将第一个2前的的所有0放在最前面，然后紧跟所有的1，后面的2和0就按照原顺序即可。方法1：暴力。方法2：借用vetctor。

代码如下：

1 //方法一 2 //#include 
      
        3 //using namespace std; 4 // 5 //const int maxn = 1e5 + 7; 6 //int a[maxn]; 7 //string s, t; 8 // 9 //int main() {10 //    cin >>s;11 //    int cnt1 = 0, cnt2 = 0, cnt3 = 0;12 //    int pos = -1;13 //    for(int i = 0; i 
       
        = pos; i--) {20 //        if(s[i] == '0') {21 //            cnt1++;22 //            if(cnt3 > 0) {23 //                for(int j = 0; j < cnt3; j++) {24 //                    t += '2';25 //                }26 //                cnt3 = 0;27 //            }28 //        } else if(s[i] == '1') {29 //            cnt2++;30 //        } else if(s[i] == '2') {31 //            cnt3++;32 //            if(cnt1 > 0) {33 //                for(int j = 0; j 
        
         59 using namespace std;60 61 string s;62 vector
         
           v;63 64 int main() {65     cin >>s;66     int cnt = 0;67     for(int i = 0; i < s.size(); i++) {68         if(s[i] == '1') cnt++;69         else v.push_back(s[i]);70     }71     int flag = 0;72     for(int i = 0; i < v.size(); i++) {73         if(v[i] == '2' && !flag) {74             while(cnt--) {75                 cout<<"1";76             }77             cout <<"2";78             flag = 1;79         } else {80             cout <
         
        
       
      

 

C. Annoying Present 题目：

题意：有n个元素，初始为0，进行m次操作，每次操作给你x和d，你选择一个i，然后对每个元素（记为j，包括i）进行操作ai+x+d*dist(i,j)，问最后所有元素的最大平均值是多少。

思路：这个就是个贪心+公式题。这题的贪心方法是当d>0时，i选择最左（最右都可以，因为dist(i,j)是一样的，最后是算平均值，所有加在哪个元素上是没有区别的；当d<0时，选择最中间，此处要将n分奇偶，因为奇数和偶数是有所区别的。当推出这些之后会发现这题就是个等差数列求和，注意会爆int，比赛的时候就是被这个点坑死。ps.赛后这题是被hack人数最多的，本场hack数排第一的大佬就是这题hack了600多人，第一个坑点就是求和不能用double，会有精度损失，第二个坑点就是不要先除，要先求和再除。

代码实现如下：

1 #include 
      
        2 using namespace std; 3  4 typedef long long ll; 5 ll n, m, x, d, ans; 6  7 int main() { 8     scanf("%I64d%I64d", &n, &m); 9     while(m--) {10         scanf("%I64d%I64d", &x, &d);11         ans += x * n;12         if(d > 0) {13             ans += (n - 1) * n / 2 * d;14         }  else {15             if(n & 1) ans += (n / 2 + 1) * (n / 2) * d;16             else ans += (n / 2) * (n / 2) * d;17         }18     }19     printf("%.8f\n", ans * 1.0 / n);20     return 0;21 }
      

 

D. Relatively Prime Graph 题目：

题意：构造一个只有n个点m条边的联通图，且相邻节点的编号要互质。

思路：当m<n-1时，由图联通知至少需要n-1条边，因此此处为impossible。1与所有的数都互质，所以此处保证了联通性。因为只需要m条边，由欧拉函数可以证得此题暴力的复杂度是稍大于O(m),我只会估算，具体证明暂时不会……因此此题可以暴力水过。

代码如下：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 using namespace std; 6  7 const int maxn = 1e5 + 7; 8 int n, m, t; 9 10 struct node {11     int x, y;12 }edge[maxn];13 14 int main() {15     cin >>n >>m;16     if(n - 1 > m) {17         puts("Impossible");18         return 0;19     }20     int flag = 0;21     for(int i = 1; i <= n; i++) {22         for(int j = i + 1; j <= n; j++) {23             if( __gcd(i, j) == 1) {24                 edge[t].x = i;25                 edge[t].y = j;26                 t++;27                 if(t >= m) {28                     flag = 1;29                     break;30                 }31             }32         }33         if(flag) break;34     }35     if(flag) {36         puts("Possible");37         for(int i = 0; i < m; i++) {38             cout <
          
           <<" " <
           
            <
           
          
         
        
       
      

 

---

 

赛后补题

E. Intercity Travelling 题目：

题意：Leha从数轴的0到n，中间的整数点都有可能有休息点也可能没有休息点。当你连续坐k站时，每两站间的疲劳值为a1,a2……ak，如果第k站有休息点，那么你可以在此处休息，然后接下来的站点的疲劳值又从a1开始，否则继续为ak+1。题目给你n和ai，每个站点有休息点的概率都是1/2，问你期望值*2^(n-1)的值。

思路：我们知道从0到1的疲劳值一定为a1，1到2的疲劳值为a1(1/2),a2(1/2)，括号里面为概率，当1有休息点时为a1，否则为a2；2到3的疲劳值为a1(1/2),a2(1/4),a3(1/4)……以此类推得到下图：

然后将他们加起来乘以2^（n-1)即可。ps.别用cin,cout，会T9，别问我怎么知道的！

代码实现如下：

1 #include 
      
        2 using namespace std; 3  4 typedef long long ll; 5 const int mod = 998244353; 6 const int maxn = 1e6 + 7; 7 int n; 8 ll ans; 9 ll a[maxn], p[maxn];10 11 int main() {12     scanf("%d", &n);13     p[0] = 1;14     for(int i = 1; i <= n; i++) {15         p[i] = p[i-1] * 2 % mod;16     }17     for(int i = 1; i <= n; i++) {18         scanf("%I64d", &a[i]);19     }20     ans = a[n];21     for(int i = 1; i < n; i++) {22         ans = (ans + (a[i] * (p[n - i] + p[n - i - 1] * (n - i) % mod) % mod) % mod) % mod;23     }24     printf("%I64d\n", ans);25     return 0;26 }