2021 ICPC 江西省大学生程序设计竞赛（正式赛）K签到#include<bits/stdc++.h>using namespace std;int main(){    int t ;    cin>>t;    while(t--){            int n,m;    cin>>n>>m;    long long sum=0;    for(int i=1;i<=n;i++){        sum+=i*i*m;    }    cout<<sum<<endl;    }}B类似于牛客原题，但是和牛客的那题过程反过来。#include<bits/stdc++.h>using namespace std;const int N=1000010;typedef long long ll;void solve(){    int x,y;    cin>>x>>y;    int cnt=0;    vector<int> ans;    while(y!=0){        ans.push_back(x/y);        int tmp=x;        x=y;        y=tmp%y;    }    cout<<ans.size()-1<<" ";    for(int i=0;i<ans.size();i++){        cout<<ans[i]<<" ";    }    cout<<endl;    }int main(){    int  T;    cin>>T;    while(T--){        solve();    }    return 0;}L差分前缀和，其实就跟x的坐标有关系。#include<bits/stdc++.h>using namespace std;const int N=1000010;typedef long long ll;int a[N];int main(){    int x1,x2,y1,y2,n;    memset(a, 0, sizeof(a));    cin>>n;    while(n--){        cin>>x1>>y1>>x2>>y2;        a[x1+1]+=1;        a[x2+1]-=1;    }    int ans=0;    for(int i=1;i<=1000000;i++){        a[i]=a[i-1]+a[i];        if(a[i]) ans++;    }    cout<<ans<<endl;    return 0;}H博弈。找规律，但是其实我们队有点带猜的味道，一猜就过了。代码：#include<bits/stdc++.h>using namespace std;int main(){    int t;    cin>>t;    while(t--){        int n,k;        cin>>n>>k;        if(n>=2&&n<=k+1)puts("pllj");        else puts("freesin");    }}F汉诺塔问题，但是是高精度，所以只能用Python了，我们语法都不记得，在比赛中硬生生凑出来了这题的语法。n个盘都可以分解为 将 x 个移到 B，y个移到 C,保证 x+y=n-1;然后将一个移到 D ，B的移到 D ，C移到D；三个碟子的汉诺塔我们都知道结论，就是2^n-1;暴力枚举 x,y;这样做似乎已经可以了，但是比赛时我们当时写的python超时了，赛后看别人的代码，别人又过了。我们当时没有预处理 2 的次方 用 ** ，然后超时了但最后我们还是过了，我们在枚举 x ，y 的时候，我们发现了 最优解的那对 x，y是有规律的。代码：n = int(input())a=list()b=list()b.insert(0,0)i=1while((i*i+i)<=40000):    b.insert(i,int((i*i+i)/2))    i=i+1a.insert(0,0)a.insert(1,1)a.insert(2,3)a.insert(3,5)i=4j=1while(i<=10000):    while(i>=b[j]):        j=j+1    j=j-1    a.insert(i,(a[i-j]+2**(j-1))*2-1)    i=i+1while(n!=0):    x=int(input())    print(a[x])    n=n-1A给一个 n * m 的0,1矩阵，从（1,1）开始到（n,m）有多少条路径至少有p 个0，q个1的路径。赛时基本都知道是DP，但是对于状态表示，状态转移没有想法，所以当时我们去写别的题目了 ，最后在那个 F的汉诺塔 Python 写了很久 （主要是py语法不是很熟 ）解题思路：我们用 dp[i][j][k]dp[i][j][k]dp[i][j][k] 表示 在（i,j）（i,j）（i,j）处 0 的个数恰好为 k 的路径数（我们当时好连这个都没有想到~~~可能没有做过 类似的题目吧）有了状态表示，转移方程很容易得到。a[i][j]=0,dp[i][j][k]=dp[i−1][j][k−1]+dp[i][j−1][k−1]a[i][j]=0,dp[i][j][k]=dp[i-1][j][k-1]+dp[i][j-1][k-1]a[i][j]=0,dp[i][j][k]=dp[i−1][j][k−1]+dp[i][j−1][k−1]a[i][j]=1,dp[i][j][k]=dp[i−1][j][k]+dp[i][j−1][k]a[i][j]=1,dp[i][j][k]=dp[i-1][j][k]+dp[i][j-1][k]a[i][j]=1,dp[i][j][k]=dp[i−1][j][k]+dp[i][j−1][k]但是 O(nm(n+m)O(nm(n+m)O(nm(n+m)的空间复杂度是不被允许的，在做状态转移的时候，可以发现当前位置得状态只跟上一行和当前行有关系 ，于是我们就可以采用滚动数组的形式，变成2m(n+m)的空间代码：#include<bits/stdc++.h>using namespace std;#define fi first#define se second#define endl '\n'typedef long long ll;const int N=5e5+10;const int M=1e6+7;const int mod=998244353;int a[505][505],dp[2][501][1001];//dp[i][j][k]表示到 [i,j]这个位置0的个数为 k的路径数int main(){ int n,m,p,q; cin>>n>>m>>p>>q; for(int i=1;i<=n;i++){  for(int j=1;j<=m;j++){   cin>>a[i][j];  } } if(p+q>=n+m){  puts("0");  return 0; } dp[0][1][a[1][1]==1? 1:0]=1; int op=1; for(int i=1;i<=n;i++){  op^=1;  for(int j=1;j<=m;j++){   if(i==1&&j==1) continue;   for(int k=0;k<=i+j-2;++k){    dp[op][j][k+a[i][j]]+=dp[op^1][j][k];//当前行    dp[op^1][j][k]=0;//置为0，滚动数组，下一次继续使用    dp[op][j][k+a[i][j]]%=mod;    dp[op][j][k+a[i][j]]+=dp[op][j-1][k];//，上一行     dp[op][j][k+a[i][j]]%=mod;   }  } } ll ans=0; for(int i=q;i<n+m;i++){  if(n+m-i-1-p>=0) ans+=dp[op][m][i],ans%=mod; } cout<<ans<<endl;  return 0;}