累惹。

 

B. Harvest of Apples

题目传送门：

题意：求∑(i=0,m) C(n,m)。

分析：定义S(n,m)=∑(i=0,m) C(n,m)。可以知道：

S(n,m)=S(n,m-1)+C(n,m)，S(n-m)=S(n-1,m-1)+S(n-1,m)=2*S(n-1,m-1)+C(n-1,m)。

由此可以推导出，由S(n,m)到S(n-1,m)，S(n+1,m)，S(n,m-1)，S(n,m+1)的式子为：

S(n-1,m)=(S(n,m)+C(n-1,m))/2

S(n+1,m)=2*S(n,m)-C(n,m)

S(n,m-1)=S(n,m)-C(n,m)

S(n,m+1)=S(n,m)+C(n,m+1)

得到了四个方向的状态转移式，因此，可以用莫队离线处理。

1 #include
      
        2 using namespace std; 3 const int maxn=1e5+10; 4 const int mod=1e9+7; 5 typedef long long ll; 6 struct point{ 7     int n,m,block,id; 8 }q[maxn];  9 ll fac[maxn],inv[maxn],ans[maxn];10 int res,Block;11 void init(){12     inv[0]=inv[1]=1;13     for (int i=2;i
       
        > t;24     Block=(int)(sqrt(t));25     for (int i=0;i
        
         > q[i].n >> q[i].m;27         q[i].id=i;28         q[i].block=q[i].n/Block;29     }30     sort(q,q+t,comp);31     ll n=0,m=0,nc=1,res=1;32     for (int i=0;i
         
          n){40             res=(res*2%mod-nc+mod)%mod;41             nc=nc*(n+1)%mod*inv[n+1-m]%mod;42             n++;43         }44         while (nm
          
           m){51             nc=nc*(n-m)%mod*inv[m+1]%mod;52             res=(res+nc)%mod;53             m++;54         }55         ans[q[i].id]=res;56     }57     for (int i=0;i
          
         
        
       
      

 

D. Nothing is Impossible

题目传送门：

题意：有若干道题，每题有1个正确选项，b个错误选项，问一个最优决策使得winner得分最大。

分析：如果仅有 1 道题，至少有一个人做对这题需要有 错误答案个数 + 1 个人。那么容易发现在每道题正确答案只有一个的情况下，如果 nn 道题中存在 ss 道题，使得学生人数 mm 不少于每道题 错误答案个数 + 1 相乘的结果，那么一定有人能够得到 ss 分。故我们将题目按错误答案个数从小到大排序，找到最大的 pp 满足就是答案。

1 #include
      
        2 using namespace std; 3 const int N=110; 4 struct node{
    int a,b,num;}a[N]; 5 bool cmp(node a,node b){
    return a.num
      

 

E. Matrix from Arrays

题目传送门：

题意：根据题意构造一个矩阵，求子矩阵和。

分析：打表发现矩阵有循环节。n为奇数时循环节为n*n，n为偶数时循环节为2*n*2*n。求出循环节二维前缀和，再扩展到普通矩阵求和即可。

1 #include
      
        2 #include
       
         3 #define maxn 500 4 using namespace std; 5 typedef long long ll; 6 int mp[maxn][maxn],a[maxn]; 7 int L; 8 void init(){ 9     int cursor = 0;10     for (int i = 0;i<4*L; ++i) {11         for (int j = 0; j <= i; ++j) { 12             mp[j][i - j] = a[cursor];13             cursor = (cursor + 1) % L;14         }15     }16     L*=2;17     for (int i=0;i
        
         > l1 >> r1 >> l2 >> r2;34     res=calc(l2,r2)-calc(l1-1,r2)-calc(l2,r1-1)+calc(l1-1,r1-1);35     return res;36 }37 int main(){38     ios::sync_with_stdio(false);39     cin.tie(0);cout.tie(0);40     int t,q;41     cin >> t;42     while (t--){43         cin >> L;44         for (int i=0;i
         
          > a[i];45         init();46         cin >> q;47         while (q--){48             ll ans=slove();49             cout << ans << endl;50         }51     }52     return 0;53 }
         
        
       
      

 

K. Expression in Memories

题目传送门：

题意：在？处填入数字0-9或+，*使得表达式合法。

分析：填入1或+即可。

1 #include
      
        2 using namespace std; 3 bool is1(char c){ 4     return c=='+'||c=='*'; 5 } 6 int main(){ 7     std::ios::sync_with_stdio(false);  8     int t;string s;cin>>t; 9     while(t--){10         cin>>s;s='+'+s;int len=s.size();11         for(int i=1;i
      

 

L. Graph Theory Homework

题目传送门：

题意：起点1，终点n，中间可经过任意点。求1-n的最小距离。

分析：容易证明：|sqrt(a)| + |sqrt(b)| > |sqrt(a+b)| ，边权满足三角不等式，故直接从1-n距离最小。

1 #include
      
        2 #include
       
         3 #include
        
          4 #define maxn 100005 5 using namespace std; 6 int a[maxn]; 7 int main(){ 8     ios::sync_with_stdio(false); 9     cin.tie(0);cout.tie(0); 10     int t,n;11     cin >> t;12     while (t--){13         cin >> n;14         for (int i=1;i<=n;i++) cin >> a[i];15         int ans=(int)sqrt(abs(a[1]-a[n]));16         cout << ans << endl;17     }18     return 0;19 }