Educational Codeforces Round 141 (Rated for Div. 2)（B，C，D）
B
这个题的大意是我们需要构造一个矩阵，我们需要这个矩阵的一个位置和它相邻位置的绝对值的不同数量最多
我猜测到这些差值为1到n*n-1，每一个数都要出现，我在做题的时候想了好多，最后还是没写出来，o(╥﹏╥)o
对于这些差值，我们可以先看一维的
我们可以是这样（当n=3）
9 1 8 2 7 3 6 4 5
这些差值有（8,7,6,5,4,3,2,1）
要把这个一维的变成二维，可以通过蛇形矩阵的方式构造，就可以了(头尾相接， 2和7是在同一列)
#include <iostream>
using namespace std;
const int maxn=50+10;
int n,m;
int a[maxn][maxn];
void solve()
{
cin>>n;
int flag=1;
int mx=n*n,mi=1;
for (int i=1;i<=n;i++)
{
if (i&1)
{
for (int j=1;j<=n;j++)
{
if (flag)
{
a[i][j]=mx;
mx--;
}
else
{
a[i][j]=mi;
mi++;
}
flag^=1;
}
}
else
{
for (int j=n;j>=1;j--)
{
if (flag)
{
a[i][j]=mx;
mx--;
}
else
{
a[i][j]=mi;
mi++;
}
flag^=1;
}
}
}
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++)
{
cout<<a[i][j]<<" ";
}
cout<<'\n';
}
return ;
}
int main ()
{
int t;
cin>>t;
while (t--)
{
solve();
}
system ("pause");
return 0;
}
C
题目大意是有1到n个人，我们要和这n个人进行比赛，（n个人之间也会相互进行比赛），还会给我们一个m
但是我们和这n个人的规则是m>=a[i]，那么我赢了,否则，我输了
而这n个人之间的规则是谁的下标大，谁就赢了
排名方式为比较胜出的常数，还有数量相同的情况，如下
1号胜出2场，2号胜出2场，3号胜出1场，那么1号，2号第一名，3号第三名
我们需要知道我可以得到的最高排名
我之前一直在纠结我看的那个题解里面的一行代码为什么要那么判断？后来看了另外一个题解才真正明白其中的意思
我们可以选择k个人（a[i]前k小的数，这个是我们可以赢的最多的人了）
我们赢了k个人，那么对于1到k个人，他的下标为i,都只能赢i-1场，我们可以赢k场（我要想更高的名次，只有让那个可以胜出k+1场的人（k+1号）变成k场，和我一样，那么我的名次就和k+1一样了）
如果这k个人的下标都是小于等于k,那么每一个人赢的场数为，此时k=3,我不可以赢4号
| 1(败给我) | 2（败给我） | 3（败给我） | 4（赢我） | 5（赢我） |
|---|---|---|---|---|
| 0 | 1 | 2 | 4 | 5 |
我赢了3场，那么我的排名就是第3名
如果是下面这个情况
| 1（败给我） | 2（赢我） | 3（败给我） | 4（败给我） | 5（赢我） |
|---|---|---|---|---|
| 0 | 2 | 2 | 3 | 5 |
那么此时我的排名就和4号一样，是第二名
所以我们就要判断k+1号在不在我选择的那k个人中
如果在ans=n-k
否则ans=n-k+1
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=5e5+10;
int a[maxn],sum[maxn];
int t,n,m;
void solve()
{
cin>>n>>m;
for (int i=1;i<=n;i++)
{
cin>>a[i];
sum[i]=a[i];
}
sort(sum+1,sum+1+n);
for (int i=1;i<=n;i++)
{
sum[i]=sum[i-1]+sum[i];
}
int k = upper_bound(sum + 1, sum + n + 1, m) - sum - 1;//1到k是我们可以战胜的的各个数
if (k == 0) cout << n + 1 << '\n';//如果我们我们找不到可以战胜的数，那么只能是最后一名了
else if (k == n) cout << 1 << '\n';//如果所有的我们都可以战胜，那么我们一定是第一名
else if (sum[k - 1] + a[k + 1] <= m) cout << n - k << '\n';//判断a[k+1]在那k个里面
else cout << n - k + 1 << '\n';
return ;
}
int main ()
{
cin>>t;
while (t--)
{
solve();
}
system ("pause");
return 0;
}
这个我想了蛮久的，哎
D
有一个长度为n的数组，我们可以进行n-2个下面的操作
如第一个操作有两种方式
a1+=a2
a3-=a2
或者是
a1-=a2
a3+=a2
我们要知道n-2个操作后有多少个不同的数组（操作要按顺序来，先1后一个是2这样的）
又见dp
我们知道最多可以有2的n-2次方，但是如果这一个操作的ai是0，那么就可能重复了
我们可以在转移的时候判断一下，如果要改变的值是0的话，就不用加两次了
还有，我们可能考虑到会出现负数的形式，我们用hash来表达（300）
对于这个一数的范围是0到300，因为ai的范围是0到300，上一个最大是300，极端的看，如果这一个是0，而我们要进行减的是300，那么这个数就会变成-300,所以hash值为300，保证数组一定不会大于300
状态转移方程为
f[i+1][a[i+1]-j+hs]=(f[i+1][a[i+1]-j+hs]+f[i][j+hs])%mod;
if (j==0) continue;//如果这一次要相加减的值为0，就不用了重复了
f[i+1][a[i+1]+j+hs]=(f[i+1][a[i+1]+j+hs]+f[i][j+hs])%mod;
#include <iostream>
using namespace std;
#define int long long
const int maxn=300+10;
const int mod=998244353;
const int hs=300*300;
int n,m,t;
int a[maxn];
int f[maxn][(hs<<1)+10];
void solve()
{
cin>>n;
for (int i=1;i<=n;i++)
{
cin>>a[i];
}
f[2][a[2]+hs]=1;
for (int i=2;i<n;i++)
{
for (int j=-1*hs;j<=hs;j++)//上一个a[i]是j的情况
{
f[i+1][a[i+1]-j+hs]=(f[i+1][a[i+1]-j+hs]+f[i][j+hs])%mod;//进行加法
if (j==0) continue;
f[i+1][a[i+1]+j+hs]=(f[i+1][a[i+1]+j+hs]+f[i][j+hs])%mod;//进行减法
}
}
int ans=0;
for (int i=-hs;i<=hs;i++)
{
ans=(ans+f[n][i+hs])%mod;
}
cout<<ans<<'\n';
return ;
}
signed main ()
{
t=1;
while (t--)
{
solve();
}
system ("pause");
return 0;
}