A. 符号化方法初探
看最大数和最小数的绝对值大小，用至多 \(n-1\) 次让其符号相同，是正数就加前一个数，是负数就倒着加后一个数，最多
\(n-2\) 次。
点击查看代码
#include<bits/stdc++.h>
const int maxn=2e5+10;
using namespace std;
int n,a[maxn],x[maxn],y[maxn],cnt,minn,maxx,ma,mi;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
maxx=-2e9;
minn=2e9;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(a[i]>maxx) maxx=a[i],ma=i;
if(a[i]<minn) minn=a[i],mi=i;
}
if(-minn>maxx)
{
for(int i=1;i<=n;i++)
{
if(a[i]>0)
{
// a[i]+=minn;
x[++cnt]=mi,y[cnt]=i;
}
}
for(int i=n-1;i>=1;i--)
{
// a[i]+=a[i+1];
x[++cnt]=i+1,y[cnt]=i;
}
}
else
{
for(int i=1;i<=n;i++)
{
if(a[i]<0)
{
// a[i]+=maxx;
x[++cnt]=ma,y[cnt]=i;
}
}
for(int i=2;i<=n;i++)
{
// a[i]+=a[i-1];
x[++cnt]=i-1,y[cnt]=i;
}
}
cout<<cnt<<'\n';
for(int i=1;i<=cnt;i++)cout<<x[i]<<" "<<y[i]<<'\n';
return 0;
}
/*
4
-1 -1 0 -1
*/
B. 无标号 Sequence 构造
思维题，\(n^3\) 暴力肯定不行，但他只问相不相等，所以我们可以构造一个 \(1*n\) 的矩阵，由于矩阵乘法满足结合率，所以
我们先 \(n^2\) 让等号两边矩阵都乘上构造矩阵再 \(n^2\) 判等即可
点击查看代码
#include<bits/stdc++.h>
const int mod=998244353;
const int maxn=3010;
using namespace std;
int t,n,a[maxn][maxn],b[maxn][maxn],c[maxn][maxn],flag,aa[2][maxn],cc[2][maxn];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>t;
while(t--)
{
flag=0;
cin>>n;
memset(aa,0,sizeof aa);
memset(cc,0,sizeof cc);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)cin>>a[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)cin>>b[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)cin>>c[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
aa[1][i]=(aa[1][i]+1ll*a[j][i]*(j%2+1)%mod)%mod;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cc[1][i]=(cc[1][i]+1ll*c[j][i]*(j%2+1)%mod)%mod;
for(int i=1;i<=n;i++)
{
long long temp=0;
for(int j=1;j<=n;j++)
{
temp=(temp+1ll*aa[1][j]*b[j][i])%mod;
// cout<<temp<<" "<<cc[1][i]<<endl;
}
if(temp!=cc[1][i])flag=1;
if(flag)break;
}
if(flag) cout<<"No"<<'\n';
else cout<<"Yes"<<'\n';
}
return 0;
}
D. 有限制的构造
一个\(dp\)，但我 \(dp\) 一直不太好
初始模型是 \(f_{i,j,k}\) 表示前 \(i\) 个，画面质量是 \(j\) ，不可玩度是 \(k\) 时的个数，但数组开不下，遂舍弃
观察到 \(n\) 最大80，所以我们可以把答案放数组里，则\(f_{i,j,k}\) 表示前 \(i\) 个，选 \(j\) 个，画面质量是 \(k\) 时，的不可玩度最小值
我们强制让 \(k\) 在范围内，最后再随便选一个即可，但 \(256MiB\)，还是开不下，滚动数组优化一下就好了
点击查看代码
#include<bits/stdc++.h>
const int maxn=1e4+10;
using namespace std;
int n,A,B,ans,a[100],b[100],f[2][82][maxn];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>A>>B;
for(int i=1;i<=n;i++)
cin>>a[i]>>b[i];
memset(f,0x7f,sizeof f);
f[1][0][0]=f[0][0][0]=0;
for(int i=1;i<=n;i++)
{
int temp=i&1;
for(int j=1;j<=i;j++)
{
for(int k=0;k<=A;k++)
{
if(k>=a[i])f[temp][j][k]=f[temp^1][j-1][k-a[i]]+b[i];
f[temp][j][k]=min(f[temp][j][k],f[temp^1][j][k]);
}
}
}
for(int i=n;i>=0;i--)
{
for(int j=0;j<=A;j++)
{
if(f[1][i][j]<=B||f[0][i][j]<=B)
{
cout<<min(i+1,n);
return 0;
}
}
}
return 0;
}