T1  chinese

根据他的问题i*f[i]我们容易联想到，答案其实是每种方案中每个点的贡献为1的加和

我们可以转变问题，每个点在所有方案的贡献

进而其实询问就是1-k的取值，有多少中方案再取个和

事实上这样做就是将每个点抽离出来，虽然每种方案中可能包含多个可行点，但是我们每次考虑的都只是一个点的贡献，所以正确

ps：指数不能取模

代码很短

1 #include
      
        2 #define int long long 3 using namespace std; 4 int n,m,K; 5 int mod=1e9+7; 6 int poww(int x,int y) 7 { 8      int ans=1; 9      while(y)10      {11          if(y&1)ans=ans*x%mod;12          x=x*x%mod;13          y>>=1;14      }15      return ans%mod;16 }17 int sum=0;18 signed main()19 {20     scanf("%lld%lld%lld",&n,&m,&K);        21     int zz=poww(K,n*m-n-m+1);22     int two=(n-1)+(m-1);23     for(int k=2;k<=K;++k)24     {25         int xx=poww(k-1,two);26         sum=(sum+(xx*zz)%mod)%mod;27     }28     printf("%lld\n",sum*n%mod*m%mod);29 }
      

 

T2 physics

正解没打，咕了

用暴力剪枝水过的

剪枝一:处理前缀和后O(1)查询，但是因为每次改变的值很小

修改时只需判断修改符号是否在上一轮的答案中，是则输出答案，否则修改

剪枝二：每次二分的长度右边界都是上一轮的答案

1 #include
      
        2 #define int long long 3 #define MAXN 2011 4 using namespace std; 5 int n,m; 6 char a[MAXN][MAXN]; 7 int sum[MAXN][MAXN]; 8 int last_x,last_y,last_len; 9 int zuo_x,zuo_y;10 int get_sum1(int x1,int y1,int x2,int y2)11 {12     return sum[x2][y2]+sum[x1-1][y1-1]-sum[x2][y1-1]-sum[x1-1][y2];13 }14 int work(int mid)15 {16     for(int i=1;i<=n-mid+1;++i)17     {18         for(int j=1;j<=m-mid+1;++j)19         {20             if(get_sum1(i,j,i+mid-1,j+mid-1)==0)21             {22                 last_x=i,last_y=j;last_len=mid;23                 return 1;24             }25         }26     }27     return 0;28 }29 void second_divied()30 {          31     int l=1;int r=last_len;32     while(l+1
       
        >1;35           if(work(mid))l=mid;36           else r=mid;   37     }38     if(work(r))printf("%lld\n",r);39     else if(work(l))printf("%lld\n",l);40 }          41 int q;int ok=0;42 void the_yu(int x,int y)43 {44      for(int i=x;i<=n;++i)45      {46          for(int j=y;j<=m;++j)47          {48              sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];49              if(a[i][j]=='-')sum[i][j]++;50          }51      }52 }53 bool pan(int x,int y)54 {55      if(x>=last_x&&y>=last_y&&x<=last_x+last_len-1&&y<=last_y+last_len-1)return 0;56      return 1;57 }58 signed main()59 {60     scanf("%lld%lld%lld",&n,&m,&q);last_len=min(n,m);61     for(int i=1;i<=n;++i)scanf("%s",a[i]+1);62     zuo_x=0x7fffff;zuo_y=0x7ffff;    63     for(int i=1;i<=q;++i)64     {65        int x,y;66        scanf("%lld%lld",&x,&y);67        a[x][y]='-';68        zuo_x=min(zuo_x,x);zuo_y=min(zuo_y,y);69        if(i>1&&pan(x,y))70        {71            printf("%lld\n",last_len);72            continue;73        }74        else75        {76            if(i==1)the_yu(1,1);77            else the_yu(zuo_x,zuo_y);78            second_divied();79            zuo_x=0x7fffff;zuo_y=0x7fffff;80        }81     }82 }
       
      

 

T3 chemistry

概率期望，仿佛不可做，咕了....