2021年ICPC江西省赛——部分个人题解

A

https://codeforces.com/gym/406715/problem/A

题意：

给定一个n * m的01矩阵，求从（1，1）到（n，m）的所有路径中，至少有p次0和q次1的路线数。

思路：

容易看到，如果单纯的dfs()，绝对超时，所以考虑是不是与dp有关；

首先考虑到可以用f[i][j][k][l]表示从起点开始到点（i， j），并且走过了k个0，l个1的路径数；

对于它的第一步优化：在01矩阵中，从（1，1）到任意一点的任意一个路线，当经过0的数量确定时，经过1的数量即为i j-1-k，所以这个dp首先可以优化成f[i][j][k]表示走到第i行第j列时，经过k次0方案数。

由此可以推出其状态转移方程：

1.当a[ i ][ j ] == 0时，f[ i ][ j ][ k ] = f[ i - 1 ][ j ][ k - 1 ] f[ i ][ j - 1 ][ k - 1 ];
2.当a[ i ][ j ] == 1时，f[ i ][ j ][ k ] = f[ i - 1 ][ j ][ k ] f[ i ][ j - 1 ][ k ];

但是当n=m=500，k=1000时，三维数组需要大量的空间，所以我们需要在进行一轮压缩;
注意到，其实转移只可能是从当前点所在行的上一行，和当前行两行转移，那么可以把i改成2，就两种状态，初始状态，当第一个点为1，那么，dp[1][1][0] = 1, 第一个1也可以是0，随便假设，第二个就是列数，第三个就是走过0个0，反之dp[1][1][1] = 0;

类似于背包问题中的二维压一维；

最后AC代码如下：

1.  
   #include<bits/stdc .h>
2.  
   using namespace std;
3.  
   const int N = 510, mod = 998244353;
4.  
   typedef long long ll;
5.  
    
6.  
   int n, m, p, q;
7.  
   int a[N][N];
8.  
   ll f[N][N*3];//注意N * 3;
9.  
    
10.  
    int main()
11.  
    {
12.  
    cin >> n >> m >> p >> q;
13.  
     
14.  
    for(int i = 1; i <= n; i )
15.  
    for(int j = 1; j <= m; j )
16.  
    cin >> a[i][j];
17.  
     
18.  
    if(!a[1][1]) f[1][1] = 1;
19.  
    else
20.  
    f[1][0] = 1;
21.  
     
22.  
    for(int i = 1; i <= n; i )
23.  
    {
24.  
    for(int j = 1; j <= m; j )
25.  
    {
26.  
    for(int k = i j - 1; k >= 0; k -- )
27.  
    {
28.  
    if(i == 1 && j == 1) continue;
29.  
    if(a[i][j]) f[j][k] = (f[j][k]%mod f[j - 1][k] % mod) % mod;
30.  
    else
31.  
    {
32.  
    if(k) f[j][k] = (f[j][k - 1]%mod f[j - 1][k - 1]%mod) % mod;
33.  
    }
34.  
    }
35.  
    if(!a[i][j]) f[j][0] = 0;
36.  
    }
37.  
    }
38.  
     
39.  
    ll res = 0;
40.  
    for(int i = 1; i <= m n - 1; i )
41.  
    {
42.  
    if(i >= p && m n - 1 - i >= q)
43.  
    res = (res f[m][i]) % mod;
44.  
    }
45.  
     
46.  
    cout << res << "\n";
47.  
    return 0;
48.  
    }

B

https://codeforces.com/gym/406715/problem/B

题意：给定一个x一个y，将x/y化简成如下图式子:

如：

 思路：可以模拟：对第一个样例分析——：105 / 38，a[ 0 ]显然是 x / y ，右式a[ 1 ]为 y / (x % y)；。

AC代码如下：

1.  
   #include<bits/stdc .h>
2.  
   using namespace std;
3.  
   const int N=1e5 10;
4.  
   int ans[N];
5.  
   void solve()
6.  
   {
7.  
   int a,b;
8.  
   int cnt=0;
9.  
   cin>>a>>b;
10.  
    while(1)
11.  
    {
12.  
    ans[cnt ]=a/b;
13.  
    int temp;
14.  
    temp=b;
15.  
    b=a%b;
16.  
    a=temp;
17.  
    if(a==1)
18.  
    break;
19.  
    }
20.  
    cout<<cnt-1<<" ";
21.  
    for(int i=0;i<cnt;i )
22.  
    cout<<ans[i]<<" ";
23.  
    cout<<endl;
24.  
    }
25.  
    int main()
26.  
    {
27.  
    int t;
28.  
    cin>>t;
29.  
    while(t--)
30.  
    {
31.  
    solve();
32.  
    }
33.  
    return 00;
34.  
    }

K

https://codeforces.com/gym/406715/problem/K

题意：有t组输入，每组输入一个n，一个m，表示有n层，第i层有i*i个房间，每个房间有m个人，求有多少人。

思路：数据小，暴力求和即可

AC代码：

1.  
   #include<bits/stdc .h>
2.  
   using namespace std;
3.  
   void solve()
4.  
   {
5.  
   int n,m;
6.  
   cin>>n>>m;
7.  
   long long ans=0;
8.  
   for(int i=1;i<=n;i )
9.  
   {
10.  
    ans =i*i;
11.  
    }
12.  
    ans*=m;
13.  
    cout<<ans<<endl;
14.  
    }
15.  
    int main()
16.  
    {
17.  
    int t;
18.  
    cin>>t;
19.  
    while(t--)
20.  
    solve();
21.  
    return 0;
22.  
    }

L

https://codeforces.com/gym/406715/problem/L

题意：给定n个板子，每个板子是从x1，y1伸展到x2，y2。有雨会从正上方下来，询问有多少长度的坐标轴是淋不到雨的。

思路：显然，坐标y对结果不会产生影响，所以我们先用x1与x2排序，然后只需要维护每个板子的x2为last，然后与下一个板子的x2比较——有两种情况：

1、q[i].x2 <= last

 2、q[i].x2 > last

则有：

AC代码：

1.  
   #include<bits/stdc .h>
2.  
   using namespace std;
3.  
   const int N=1e6 10;
4.  
   struct node
5.  
   {
6.  
   int x1;
7.  
   int y1;
8.  
   int x2;
9.  
   int y2;
10.  
    }q[N];
11.  
    bool cmp(node n1,node n2)
12.  
    {
13.  
    return n1.x1<n2.x1;
14.  
    }
15.  
    int main()
16.  
    {
17.  
    int n;
18.  
    int a,b,c,d;
19.  
    scanf("%d",&n);
20.  
    for(int i=0;i<n;i )
21.  
    {
22.  
    cin>>a>>b>>c>>d;
23.  
    if(a<c)
24.  
    {
25.  
    q[i].x1=a;
26.  
    q[i].y1=b;
27.  
    q[i].x2=c;
28.  
    q[i].y2=d;
29.  
    }
30.  
    else
31.  
    {
32.  
    q[i].x1=c;
33.  
    q[i].y1=d;
34.  
    q[i].x2=a;
35.  
    q[i].y2=b;
36.  
    }
37.  
    }
38.  
    sort(q,q n,cmp);
39.  
    int last=q[0].x1;
40.  
    long long ans=0;
41.  
    for(int i=0;i<n;i )
42.  
    {
43.  
    if(q[i].x2<=last)
44.  
    continue;
45.  
    ans =q[i].x2-q[i].x1;
46.  
    int add=last-q[i].x1;
47.  
    if(add>0)
48.  
    ans-=add;
49.  
    last=q[i].x2;
50.  
    }
51.  
    cout<<ans;
52.  
    }
53.  
     

这篇好文章是转载于：学新通技术网