提高组模拟试题 DLC (1)
T1. 传送门 (portal)
构造，二进制
画画图就很容易想出来了
思路
- 明显，从1号传送门走到2号传送门有k种方法。使用节点数为3q+1.
- 考虑把n进行二进制拆分。
- 如下图，再构造一条含有2q+1个节点的链：
- 将k二进制拆分后，记最低位为第 0位。若第i位二进制位为1，则如图连接对应的两个点。
- 不难发现此图符合要求，使用节点数为5q+2，极限情况时大约需要使用 150个节点。
本来是AC代码，结果在第47行两个cnt和2写反了！！！只有35分
AC代码：
#include
using namespace std;
int k,a[110],s=0,n5,n4,n3,n2,n1,num=0,n;
int b[1100][5],cnt=0;
int main()
{
ios::sync_with_stdio(false);
freopen("portal.in","r",stdin);
freopen("portal.out","w",stdout);
cin>>k>>n5>>n4>>n3>>n2>>n1;
int x=k;
while(x!=0)
{
s++;
a[s]=x%2;
x=x/2;
}
for(int i=1;i<=s/2;i++)
{
swap(a[i],a[s-i+1]);
}
s=s-1;
n=2*s;
if(k==1)
{
cout<<2<<' '<<1<<endl;
cout<<1<<' '<<2<<endl;
return 0;
}
num=4*s+s;
for(int i=2;i<=s;i++)
{
if(a[i]==1)
{
cnt++;
b[cnt][1]=s*2+1+i;
b[cnt][2]=i*2+1;
cnt++;
b[cnt][1]=s*2+1+i;
b[cnt][2]=i*2+2;
num=num+2;
}
}
if(a[s+1]==1)
{
cnt++;
b[cnt][1]=s*3+2;
b[cnt][2]=2;
num++;
}
n=s*3+2;
cout<<n<<' '<<num<<endl;
cout<<1<<' '<<3<<endl;
cout<<1<<' '<<4<<endl;
for(int i=3;i<=s*2;i++)
{
cout<<i<<' '<<((i+1)/2)*2+1<<endl;
cout<<i<<' '<<((i+1)/2)*2+2<<endl;
}
cout<<s*2+1<<' '<<2<<endl;
cout<<s*2+2<<' '<<2<<endl;
cout<<1<<' '<<s*2+3<<endl;
for(int i=s*2+3;i<=s*3+1;i++)
{
cout<<i<<' '<<i+1<<endl;
}
for(int i=1;i<=cnt;i++)
{
cout<<b[i][1]<<' '<<b[i][2]<<endl;
}
return 0;
}
T2. 摆肖像 (portrait)
权值线段树
自闭了，本来以为很简单，结果想了快两个小时发现自己把题目理解错了，就只能交了一个三分钟打的暴力，还是有分
错误代码
#include
using namespace std;
inline int read(){
int x=0,f=1;char c;
do c=getchar();while(!isdigit(c)&&c!='-');
if(c=='-') f=-1,c=getchar();
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return x*f;
}
const int N=5e5+10;
int a[N];
pair b[N];
int main(){
freopen("portrait.in","r",stdin);
freopen("portrait.out","w",stdout);
int n=read(),q=read();
for(int i=1;i<=n;i++)
{
a[i]=read();
}
while(q--)
{
int pos=read(),val=read();
a[pos]=val;
for(int i=1;i<=n;i++)
{
b[i]={a[i],i};
}
sort(b+1,b+n+1);
int ans=0;
for(int i=1;i<=n;i++)
{
ans=max(ans,abs(i-b[i].second));
}
printf("%d\n",ans+1);
}
return 0;
}
T3. 选疑犯 (possibility)
简单数论
思路
考试的时候没有完全分解出来，所以就只能用快速幂来打暴力了。后面该题的时候成功做出来了。
错误代码
#include
using namespace std;
typedef long long ll;
inline ll read()
{
ll x=0,f=1;char c;
do c=getchar();while(!isdigit(c)&&c!='-');
if(c=='-') f=-1,c=getchar();
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return x*f;
}
ll Test,n,p,q,a,mod,num;
ll quick(ll a,ll b)
{
ll ans=1;
while(b){
if(b&1) ans=ans*a,ans%=mod;
a=a*a;
a%=mod;
b>>=1;
}
return ans%mod;
}
int main()
{
freopen("possibility.in","r",stdin);
freopen("possibility.out","w",stdout);
Test=read(),n=read(),p=read(),q=read(),a=read(),mod=read(),num=0;
for(ll i=0;i<=q;i++)
{
num+=(quick(a,2*i)%p)*quick(p,i);
}
ll cnt=0;
for(ll i=1;i<=num;i++)
{
ll q=i;
while(q%p==0)
{
cnt++;
cnt%=n;
q/=p;
}
}
printf("%d",cnt%n);
return 0;
}
T4. 断电源 (power)
单调队列优化动态规划
看出来是DP了！但就是不会写状态转移方程！所以就只能被迫用深搜打暴力了
代码
#include
using namespace std;
inline int read()
{
int x=0,f=1;char c;
do c=getchar();while(!isdigit(c)&&c!='-');
if(c=='-') f=-1,c=getchar();
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return x*f;
}
const int N = 1e3+10;
int n,P,ans;
struct pama
{
int r,p,h;
bool operator<(const pama x)const
{
if(x.p==p)
{
return x.rp;
}
}a[N];
void init()
{
n=read(),P=read();
for(int i=1;i<=n;i++)
{
a[i].r=read();
}
for(int i=1;i<=n;i++)
{
a[i].p=read();
}
for(int i=1;i<=n;i++)
{
a[i].h=read();
}
sort(a+1,a+n+1);
ans=0;
}
void dfs(int dep,int red,int ele,int h)
{
if(redn||(ans!=0&&ans=0 && ele<=0)
{
ans=ans==0?h:min(ans,h);
return ;
}
dfs(dep+1,red-a[dep].r,ele-a[dep].p,h+a[dep].h);
dfs(dep+1,red,ele,h);
}
int main()
{
freopen("power.in","r",stdin);
freopen("power.out","w",stdout);
int T=read();
while(T--)
{
init();
dfs(1,P,P,0);
if(!ans)
{
puts("Bad Luck");
}
else
{
printf("%d\n",ans);
}
}
return 0;
}
/*
2
5 25
1 3 6 10 13
13 7 8 15 16
2 3 10 2 7
4 1
99 82 443 53
19260 8171 9260 817
233 666 1000 1234567
*/