杭电多校第二场

1001

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

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

排列的逆序对满足$sgn(\pi)=(-1)^{n(\pi)}=\Pi_{0 \leq j <i \leq p-1}\frac{ \pi(i)-\pi(j)}{i-j}$，其中$n(\pi)$为逆序对数，可以用sgn指示奇偶性，$sgn$可化为$a^{\frac{p-1}{2}}(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;
  }
}