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=1
while((i*i+i)<=40000):
    b.insert(i,int((i*i+i)/2))
    i=i+1
a.insert(0,0)
a.insert(1,1)
a.insert(2,3)
a.insert(3,5)
i=4
j=1

while(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+1

while(n!=0):
    x=int(input())
    print(a[x])
    n=n-1

A

给一个 n * m 的0,1矩阵，从（1,1）开始到（n,m）有多少条路径至少有p 个0，q个1的路径。

赛时基本都知道是DP，但是对于状态表示，状态转移没有想法，所以当时我们去写别的题目了，最后在那个 F的汉诺塔 Python 写了很久（主要是py语法不是很熟）

解题思路：我们用 $d p [i] [j] [k]$ 表示在 $（ i, j ）$ 处 0 的个数恰好为 k 的路径数（我们当时好连这个都没有想到~~~可能没有做过类似的题目吧）

有了状态表示，转移方程很容易得到。

$a [i] [j] = 0, d p [i] [j] [k] = d p [i - 1] [j] [k - 1] + d p [i] [j - 1] [k - 1]$
$a [i] [j] = 1, d p [i] [j] [k] = d p [i - 1] [j] [k] + d p [i] [j - 1] [k]$

但是 $O (n m (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;
}