杭电多校第二场

1001

题意是给定一个整数边长的立方体，以其边上的整数点为顶点，有多少个等边三角形，要求三条边在三个坐标平面上。
容易得到，一个单位长度边长的立方体中有8个三角形，只有数共有多少立方体，显然为 ∑ i = 1 n − 1 i 3 \sum^{n-1}_{i=1}i^3 ∑i=1n−1​i3个

  long long inv2=qpow(2,mod-2);
  per(){
    long long n;cin>>n;
    n--;
    n%=mod;
    long long val=n*(n+1)%mod*inv2%mod;
    cout<<val*val%mod*8%mod<<endl;
  }

1005

模拟一遍即可，只有可同时在两边加时乘2，否则只能按位置放。

  per(){
    int n;cin>>n;
    cin>>in;
    ll ans=1;
    char lch=in[0];
    char rch=in[0];
    for(int i=1;i<n;++i){
      if(in[i]<lch){
        lch=in[i];
      }else if(in[i]==lch){
        if(rch==in[i]){
          ans=1ll*ans*2%mod;
        }
      }else{
        rch=in[i];
      }
    }
    cout<<ans%mod<<endl;
  }

1008

两个基础的dp的组合，先求出dp[i][j],即第i门课花j时间能获得的分数，然后利用这个结果求dp2[i][j],即挂i门课花j时间能获得的总分。
第一个dp实际是进行多个dp[j],每门课是独立的，实现时实际是dp[k][j]，即前k个资料，j时间这门课能得的分，利用滚动数组变成一维。
第二个dp是二维费用的分组dp，将第i门课，花1个时间得dp[i][1]分、2个时间得d[i][2]、3个时间…t个时间得到dp[i][t]分，看成t个物品，其价值为分数，一个费用是花的时间，另一个费用是是否挂科，如果这个物品的分数低于60，费用为1，否则为0。同样有前多少个物品这一维度，用滚动数组优化掉，然后进行分组dp，注意分组dp时，遍历每个物品时不能直接修改dp数组的值，因为一组只能选一个，如果立即在dp表中修改，就会出现一组选多个，而是要比较时用dp表，当前轮的结果写入一个临时表中（这样比较时不会和这组中已经修改过的结果进行比较），一轮结束后将临时表写入dp表中。注意初始化为负无穷（0xc0）。

struct ui {int fir; int sec;};
const int maxn = 1005;
int dp[50][503];
int dp2[4][503];
int tmp[4][503];
signed main()
{
  per() {
    int n; cin >> n;
    map<string, int> ma;
    string in;
    for (int i = 1; i <= n; ++i) {
      cin >> in;
      ma[in] = i;
    }
    int m; cin >> m;
    int x, y;
    vector<ui> mts[51];
    for (int i = 1; i <= m; ++i) {
      cin >> in >> x >> y;
      mts[ma[in]].push_back(ui{x, y});
    }
    int t, p; cin >> t >> p;
    for(int i=0;i<=n;++i){
      for(int j=0;j<=502;++j){
        dp[i][j]=0;
      }
    }
    for (int c = 1; c <= n; ++c) {
      int sz = mts[c].size();
      for (int i = 0; i < sz; ++i) {
        int v = mts[c][i].fir;
        int w = mts[c][i].sec;
        for (int j = t; j >= w; --j) {
          dp[c][j] = max(dp[c][j], dp[c][j - w] + v);
        }
      }
    }
    memset(dp2,0xc0,sizeof dp2);
    dp2[0][0]=0;
    for (int i = 1; i <=n; ++i) {
      memset(tmp,0xc0,sizeof tmp);
      for (int j = t;j>=0; --j) {
        int w1 = dp[i][j] < 60 ? 1 : 0;
        int w2 = j;
        int v = min(dp[i][j],100);
        for (int w = p; w >= w1; --w) {
          for (int k = t; k >= w2; --k) {
            if (w - w1 >= 0 && k - w2 >= 0)
              tmp[w][k] = max(tmp[w][k], dp2[w - w1][k - w2] + v);
          }
        }
      }
      memcpy(dp2,tmp,sizeof tmp);
    }
    int ans=-1;
    for(int i=0;i<=p;++i){
      ans=max(ans,dp2[i][t]);
    }
    cout<<ans<<endl;
  }
}

1010

排列的逆序对满足 s g n ( π ) = ( − 1 ) n ( π ) = Π 0 ≤ j < i ≤ p − 1 π ( i ) − π ( j ) i − j sgn(\pi)=(-1)^{n(\pi)}=\Pi_{0 \leq j <i \leq p-1}\frac{ \pi(i)-\pi(j)}{i-j} sgn(π)=(−1)n(π)=Π0≤j<i≤p−1​i−jπ(i)−π(j)​，其中 n ( π ) n(\pi) n(π)为逆序对数，可以用sgn指示奇偶性， s g n sgn sgn可化为 a p − 1 2 ( m o d p ) a^{\frac{p-1}{2}}(modp) a2p−1​(modp),求其值即可。注意爆ll。

LL a,P,b;
inline long long Mul(long long x,long long y){
    long long tmp=(x*y-(long long)((long double)x/P*y+1.0e-8)*P);
    return (tmp+P)%P;
}
LL qpow(LL x,LL y){
  LL re=1,re2;
  while(y){
    if(y&1) {
      re=Mul(re,x);
    }
    x=Mul(x,x);
    y>>=1;
  }
  return re;
}
int main(){
  int t;cin>>t;
  while(t--){
    LL a;cin>>a>>P;
    cout<<(qpow(a,(P-1)/2)==1? 0:1)<<endl;
  }

}

1011

一开始的想法是dp，将当前数的某个非前缀的零变1，只从多一个1的转移，但是问题有：负数没法处理，且多出多个1的数和当前数的贡献算不进去，没法弄。
所以采用题解的做法，题解做法和我的很像，不过他不是直接转移答案，而是转移这个位置上可能用到的几个最值。我原先的做法，无法做到：对于10100，计算10100和11110的贡献，因为差了2，但是现在可以做到，如果10100和11110的贡献更大，那么会把最值转移到11100再转移到10100，就算进去了，即计算乘积最值时，应该分开维护最值，这样信息能顺着任一因子传递，而不是只能成对传递（如果想灵活传递复杂度又上去了，不只是维护，而是每一轮都遍历）。

const int INF=2e9;
const ll inf=1e18;
const int maxn=1<<20;
const int mod=998244353;
int a[maxn+10],A[maxn+10];
int b[maxn+10],B[maxn+10];
ll c[maxn+10];
signed main()
{
  per(){
    int n;
    cin>>n;
    for(int i=1;i<=n;++i){
      cin>>a[i-1];
      A[i-1]=a[i-1];
    }
    for(int i=1;i<=n;++i){
      cin>>b[i-1];
      B[i-1]=b[i-1];
    }
    int m=1;
    while(m<n){
      m<<=1;
    }
    for(int i=n;i<m;++i){
      A[i]=B[i]=-INF;
      a[i]=b[i]=INF;
    }
    for(int i=1;i<m;i<<=1){
      for(int j=m-1;j>=0;j--){
        if(!(j&i)){
          A[j]=max(A[j],A[i^j]);
          B[j]=max(B[j],B[i^j]);
          a[j]=min(a[j],a[i^j]);
          b[j]=min(b[j],b[i^j]);
        }
      }
    }
    c[n]=-inf;
    for(int i=n-1;i>=0;i--){
      c[i]=-inf;
      if(A[i]!=-INF&&B[i]!=-INF)
        c[i]=max(c[i],1ll*A[i]*B[i]);
      if(A[i]!=-INF&&b[i]!=INF)
        c[i]=max(c[i],1ll*A[i]*b[i]);
      if(a[i]!=INF&&B[i]!=-INF)
        c[i]=max(c[i],1ll*a[i]*B[i]);
      if(a[i]!=INF&&b[i]!=INF)
        c[i]=max(c[i],1ll*a[i]*b[i]);
      c[i]=max(c[i],c[i+1]);
    }
    ll ans=0;
    for(int i=0;i<n;++i){
      ans=(ans+c[i])%mod;
    }
    cout<<(ans%mod+mod)%mod<<endl;
  }
}