2022“杭电杯”中国大学生算法设计超级联赛（2）个人题解

签到。

很长的阅读理解废话，跳过发现是区间排序，也算签到。

废话骗了很多人

#include  #define int long long const int maxn = 1e5   10; using namespace std; struct node { 
          int l, r;  bool operator < (const node &x) const { 
           if (l == x.l) return r < x.r;   return l < x.l;  } }a[maxn]; signed main()  { 
          ios::sync_with_stdio(0);  cin.tie(0);  int t;  cin >> t;  while (t--) { 
           int n;   cin >> n;   for (int i = 1; i <= n;  i) { 
            cin >> a[i].l >> a[i].r;
		}
		a[n + 1].l = 1e9 + 10;
		sort(a + 1, a + 1 + n);
		int cnt = 0;
		for (int i = 1; i <= n; ++i) { 
        
			if (a[i].r >= a[i + 1].l) { 
        
				break;
			}
			cnt++;
		}
		cout << cnt << endl;
	}
}

看上去是入门的 dp 问题，选纸币。但是纸币值是 $7,31,365$，数据范围到了 $1e18$.

发现 $365=5\times 31+30\times 7$, 所以优先用 $365$ 肯定是优于其他情况的。

所以先对 $n$ 取模到 $[0,365)$，然后再作 dp 即可，转移方程 $f[i]=min(f[i-7],f[i-31])+1$.

实际上暴力一点，直接对前 $7\times 31\times 365=79205$ 个数据预处理也是可以的，完全可接受。想太复杂了。

#include 
using namespace std;
using ll = long long;

int a[3] = { 
        7, 31, 365};
int nums[1010];

int main()
{ 
        
    memset(nums, 0x3f, sizeof(nums));
    nums[0] = 0;
    for (int i = 0; i < 3; i++)
        for (int j = a[i]; j <= 1000; j++)
            if (nums[j - a[i]] != 0x3f3f3f3f)
                nums[j] = min(nums[j], nums[j - a[i]] + 1);
    int t;
    cin >> t;
    while (t--)
    { 
        
        ll x;
        cin >> x;
        if (x < 365)
        { 
        
            if (nums[x] != 0x3f3f3f3f)
                cout << nums[x] << endl;
            else
                cout << -1 << endl;
        }
        else
        { 
        
            ll p = x / 365ll;
            ll q = x % 365ll;
            if (nums[q] != 0x3f3f3f3f)
                cout << p + nums[q] << endl;
            else
                cout << p - 1 + nums[q + 365] << endl;
        }
    }
}

（队友的代码）

观察式子 $x=Py\%M,y=Qx\%M$.

其实不用观察

首先由条件 $PQ\%M=1$ 可知 $(PQ-1)\%M=0$. 即有

$PQ=kM,k=1,2,...$

又由最前面的式子知道，$k$ 不可能小于 max ⁡ { P , Q } \max\{P,Q\} max{ P,Q} 的，而且一定是一个质因子。

知道是质因子就好做了，找到一个最大的满足条件的就行。

实际上也很容易证明这样的 $k$ 只有一个。

#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int maxn=2e6+10;
int prime[maxn],cnt=0;
int vis[maxn];
int mnprime[maxn];
void get_prime(int n){ 
        
    for(int i=2;i<=n;i++){ 
        
        if(!vis[i])prime[cnt++]=i;
        for(int j=0;i*prime[j]<=n;j++){ 
        
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)break;
        }
    }
}
int main(){ 
        
    int tt;
    get_prime(2000000);
    scanf("%d",&tt);
    while(tt--){ 
        
        ll p,q,e;
        cin>>p>>q>>e;
        ll xx=p*q-1;
        vector<long long>v;
        v.clear();
        for(int i=0;i<cnt;i++){ 
        
            if(xx%prime[i]==0){ 
        
                if(prime[i]>max(p,q)){ 
        
                    v.push_back(prime[i]);
                }
                while(xx%prime[i]==0)xx/=prime[i];
            }   
        }
        if(xx!=1)v.push_back(xx);
        if(v.size()==0){ 
        
            printf("shuanQ\n");
        }
        else{ 
        
            printf("%lld\n",e*q%v[0]);
        }
    }
}

（还是队友写的，数论爷 orz）

题意：

给一个树，然后给 $q$ 次询问，每次询问给三个节集 $A,B,C$，问有多少个点同时满足以下条件：

1. 点在 $A$ 中某一点到根节点 $1$ 的简单路径上
2. 点在 $B$ 中某一点到根节点 $1$ 的简单路径上
3. 点到根节点的简单路径上存在 $C$ 中某一点

数据保证 $\sum (A+B+C)<2e5$.

比赛的时候树剖调出来了，但是一直 TLE. 赛后继续 T.

自己的解法是，将树重链剖分，然后可以在 $\log$ 时间内给 $C$ 的每个节点的子树打上标记，总共花 $O(C\log n)$。然后再给 $A,B$ 每个点到根节点上的各点打上标记。由于重链剖分的性质，这个操作最多也就是 $O((A+B){\log }^{2}n)$ 的。最后再询问整个树中哪些点被打上了三个标记，$O(\log n)$.

总复杂度 $O((n+C+(A+B)\log n)\log n)$，我觉得不应该 TLE（（（ 事后看题解发现官方题解也用了这个方法，和我一模一样。教教我怎么写出常数小的树剖 qwq.

上面一段话完全是没有意识到自己怎么错了。

请看我的查询：

int exist(int k, int l, int r) { 
        
	if (a[k].l > r || a[k].r < l) return 0;
	if (a[k].l >= l && a[k].r <= r) { 
        
		if (a[k].v1 == a[k].r - a[k].l + 1 && a[k].v2 == a[k].r - a[k].l + 1 && a[k].r - a[k].l + 1 == a[k].v3)
			return a[k].r - a[k].l + 1;
	}
	if (a[k].l == a[k].r) return 0;
	pushdown(k);
	return (exist(lson, l, r) + exist(rson, l, r)); 
}