1128模拟总结

可拿分数 100+100+60+40=300

实际得分 100+ 40+10 + 40=190

T1

problem:

T次询问，每次询问判断一个数是不是某两个斐 波那契数的乘积

对于 100%的数据，1≤T≤100，0≤A≤1e9。

solution：

预处理出前40个 斐波那契数 ，n² 处理出乘积，然后O(1)查询

T2

problem：带有边权的最优贸易

solution：加超级源点，边权设为买入时的价格，跑一遍dijkstra；

T3

problem：一个n*m的数表，给定两个大小一样、不相交且没有共同的边界的矩形，并交换两个矩形内的内容。

暴力模拟swap 60分

模拟时写了个奇怪的特判，WA声一片。删掉有60分。

T4

problem：从1到N中选出不超过K个正整数，求使得这些数的乘积是一个无平方因子数的方案数

暴力深搜 40分

对于每一个数只有选或不选，判断乘积是否为无平方因子数，ans++

题目传送门

看完题面先写了一份暴力

然后竟然AC了

直接模拟

刚开始有30000个小方块

每次移动 都是把一个方块移动到另一个方块上变成一个大方块

可以发现每次移动大方块内的小方块都是先进先出，于是对于每一个方块都可以用队列维护

当我们把 一个小方块x 移动到另一方块y上时，x 下方的方块数目等于移动前 y的所含的方块数目

用d[i]表示方块i下方的方块数目，于是我们可以O（1）查询

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const int N = 30007;
queue<int> num[N]; // 队列维护 每个大方块里 的小方块 
ll v[N],cnt[N],d[N],n;// v[i] 小方块i在哪个大方块中 ， cnt[i] 大方块i有多少个小方块 ， d[i] 小方块i下方有多少个小方块 
void M(ll x,ll y)
{   
    ll a=v[x],b=v[y];//先记录 x，y 所在的 大方块编号 
    for(ll i=1;i<=cnt[a];++i)
    {   
		//将 x 移入 y 所在的方块  
        ++cnt[b];
        ll now = num[a].front();
        num[b].push(now);
        v[now]=b; 
        num[a].pop();
        // 每次移动都更新 d[i] 
		// now下方的方块数目等于移动前 b的所含的方块数目 
        d[now]=cnt[b]-1; 
    }
}
int main()
{
    n = read();
    for(ll i=1;i<=30000;++i)
    {
		//刚开始对每个小方块 初始化 
        num[i].push(i);
		v[i]=i;
		cnt[i]=1; 
    }
    for(ll i=1;i<=n;++i)
    {
        char c;cin>>c;
        if(c=='M')
        {
            ll x=read(),y=read();
            M(x,y);
        }
        else
        {
            ll x=read();
            printf("%d\n",d[x]);
        }
    }
    return 0;
}