模拟赛
今天是七夕耶！
哦，今天是七夕呀。。。
T1 Non-decreasing
题目背景
先拿部分分，当全正或全负时很显然，只需要 \(n\) 次操作：
- 正：如果 \(a_i \gt a_{i+1},a_{i+1} \gets (a_i+a_{i+1})\)。
- 负：如果 \(a_i \lt a_{i-1},a_{i-1} \gets (a_i+a_{i-1})\)。
然后开始想有正有负的情况，因为上述的做法保证只会对单一方向产生影响，而双向的会有后效性。。。
其实总操作数给到了 \(2n\) 次，而我们只需要找出绝对值最大的那个数就可以在 \(n\) 次操作内使序列变为全正或全负，然后按上面的做法就好啦。
code
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define fi first
#define se second
const int N = 2e5+5;
int n,ans;
long long a[N],b[N];
pair<int,int> op[N];
int main()
{
// freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]),b[i]=a[i];
sort(b+1,b+1+n);
if(b[1]>=0)
{
for(int i=1;i<n;i++)
{
if(a[i]>a[i+1])
{
op[++ans]=make_pair(i,i+1);
a[i+1]=a[i]+a[i+1];
}
}
printf("%d\n",ans);
for(int i=1;i<=ans;i++) printf("%d %d\n",op[i].fi,op[i].se);
}
else if(b[n]<=0)
{
for(int i=n;i>1;i--)
{
if(a[i-1]>a[i])
{
op[++ans]=make_pair(i,i-1);
a[i-1]=a[i]+a[i-1];
}
}
printf("%d\n",ans);
for(int i=1;i<=ans;i++) printf("%d %d\n",op[i].fi,op[i].se);
}
else
{
if(b[n]>=abs(b[1]))
{
int tmp=0;
for(int i=1;i<=n;i++)
{
if(a[i]==b[n])
{
tmp=i; break;
}
}
for(int i=1;i<=n;i++)
{
if(a[i]<0)
{
op[++ans]=make_pair(tmp,i);
a[i]+=b[n];
}
}
for(int i=1;i<n;i++)
{
if(a[i]>a[i+1])
{
op[++ans]=make_pair(i,i+1);
a[i+1]=a[i]+a[i+1];
}
}
}
else
{
int tmp=0;
for(int i=1;i<=n;i++)
{
if(a[i]==b[1])
{
tmp=i; break;
}
}
for(int i=1;i<=n;i++)
{
if(a[i]>0)
{
op[++ans]=make_pair(tmp,i);
a[i]+=b[1];
}
}
for(int i=n;i>1;i--)
{
if(a[i-1]>a[i])
{
op[++ans]=make_pair(i,i-1);
a[i-1]=a[i]+a[i-1];
}
}
}
printf("%d\n",ans);
for(int i=1;i<=ans;i++) printf("%d %d\n",op[i].fi,op[i].se);
}
return 0;
}
T2 矩阵
题目背景
很巧妙的一道题，我们发现 \(n^3\) 显然过不了。考虑如何优化。
因为三个矩阵都是 \(n \times n\)，人类智慧发现如果在等式左右同时左乘一个 \(1 \times n\) 的矩阵，矩乘的复杂度就变成 \(n^2\)。
然后随便做了。（据说重复几次会防止冲突，其实不用）
（还有 Hash 做法）
code
#include<bits/stdc++.h>
using namespace std;
#define scan __builtin_scanf
const int N = 3005,mod = 998244353;
int t;
int n,a[N][N],b[N][N],c[N][N],d[N],tmp[N],tmp2[N],tmp3[N];
bool check()
{
for(int i=1;i<=n;i++) tmp[i]=tmp2[i]=tmp3[i]=0;
for(int i=1;i<=n;i++) d[i]=rand()%100000+998244;
for(int k=1;k<=n;k++)
for(int j=1;j<=n;j++) tmp[j]=(tmp[j]+1ll*d[k]*a[k][j]%mod)%mod;
for(int k=1;k<=n;k++)
for(int j=1;j<=n;j++) tmp2[j]=(tmp2[j]+1ll*tmp[k]*b[k][j]%mod)%mod;
for(int k=1;k<=n;k++)
for(int j=1;j<=n;j++) tmp3[j]=(tmp3[j]+1ll*d[k]*c[k][j]%mod)%mod;
for(int i=1;i<=n;i++) if(tmp2[i]!=tmp3[i]) return 0;
return 1;
}
int main()
{
// freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
srand(time(0)); srand(rand());
scan("%d",&t);
while(t--)
{
scan("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scan("%d",&a[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scan("%d",&b[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scan("%d",&c[i][j]);
if(check()) printf("Yes\n");
else printf("No\n");
}
return 0;
}
T3 神奇纸牌
题目背景
看起来不太可做。。。
毒瘤出题人。。。
先咕着。。。
T4 Maximum Glutton
题目背景
小 trick，显然是背包，但是容积太大开不下。
经典做法是交换值域和其中一维，发现值域也只有 \(n\) 的，所有复杂度就是 \(O(n^2V)\)。
code
#include<bits/stdc++.h>
using namespace std;
#define mi(x,y) (x<y?x:y)
#define scan __builtin_scanf
#define print __builtin_printf
const int N = 81;
int n,A,B;
int f[N][10005];
int main()
{
// freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
scan("%d%d%d",&n,&A,&B);
for(int i=0;i<=n;i++) for(int j=0;j<=A;j++) f[i][j]=1e9+7; f[0][0]=0;
for(int i=1;i<=n;i++)
{
int x,y;
scan("%d%d",&x,&y);
for(int j=n;j;j--)
for(int k=A;k>=x;k--)
f[j][k]=mi(f[j][k],f[j-1][k-x]+y);
}
for(int i=n;~i;i--)
for(int j=1;j<=A;j++)
{
if(f[i][j]<=B)
print("%d\n",mi(i+1,n)),exit(0);
}
putchar('1'); putchar('\n');
return 0;
}