2022赛氪 秋季赛 补题 (鼠鼠输麻了)

题目
T2 贪心
贪心也没贪明白，当时用数组维护的，后来发现纯纯有问题啊。因为数组维护就不能动态维护时间的最小值了。所以还得用优先队列维护，时间复杂度O(nnlog(n))。只要洗锅结束的时间在t-x之前就能用。

#include
using namespace std;
#define int long long
typedef pair<int,int> PII;
PII a[5002];
priority_queue<PII,vector<PII>,greater<PII> >q;
int n,m,k,T;
int x,y,z;
signed main(void)
{
	int ans = 0;
	cin>>n>>x>>y>>z;
	for(int i=1;i<=n;++i) cin>>a[i].first>>a[i].second;
	sort(a+1,a+n+1);
	for(int i=1;i<=n;++i)
	{
		int le = a[i].second; //数量要求
		int wh = a[i].first - x - y; //什么时候做第i个订单最好
		int ddl = a[i].first - x; //最晚什么时候 
		while(q.size()&&le>0)
		{
			auto tmp = q.top();
			int t = tmp.first;
			int num = tmp.second;
			if(t<=ddl)
			{
				q.pop();
				if(le>=num)
				{
					q.push({max(wh,t)+x+z,num});
					le -= num;
				}
				else
				{
					q.push({t,num-le});
					q.push({max(wh,t)+x+z,le});
					le = 0;
				}
			}
			else 
			{
				break;
			}
		}
		if(le>0)
		{
			ans += le;
			q.push({wh+x+z,le});
		}
	}
	cout<<ans;
	return 0;
}
/*
6 100 40 70
10 1
100 2
210 3
320 4
440 5
560 6
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

T4 待补

T9 数学不好，输麻了
y=k1x
z=k2y=k1k2x
gcd(y/x,z/y) = 1，即gcd(k1,k2) = 1.
对于k1k2，可以从1到n枚举。
(1) 那么对于t = k1k2有多少个gcd(k1,k2)=1呢？
答案是2的x次幂，x是t的质因子的种类数。
因为对于t这个数的某个质因子，要么分给k1，要么分给k2，如果一部分分给k1、一部分分给k2，gcd就不是1了。
所以对于某个质因子，要么在这边要么在那边，2的次幂。233，33作为一个整体分配。
(2) 那么怎么求1到n的质因子种类数呢？如果试除法，自然太慢了。可以在线性筛的过程中维护。
如果i%prime[j]==0，此时i被他最小的质因子prime[j]筛掉，他的质因子个数和i一样，因为i已经有prime[j]这个质因子了，iprime[j]之后不会增加质因子种类。
否则，prime[j]是iprime[j]新增的质因子。
这里回想一下，线性筛里i%prime[j]==0，是说保证iprime[j]这个数每次被筛恰好被其最小的质因数筛掉。这样前边质因子种类才能求得顺理成章。
(3) 除此之外，对于t=k1*k2=1…2…3，1-n中有多少种组合呢？
答案: 有n/i种，即1-n中有多少个数是t的倍数，t = 3,z = 3、6、9…

#include
using namespace std;
typedef long long ll;
const int N = 1e7+10;
const int mod = 998244353;
bool vis[N];
int prime[N];
int d[N]; //质因子的个数 
int a[12];
int tot = 0,n;
void init(int n)
{
	memset(vis,1,sizeof(vis));
	for(int i=2;i<=n;++i)
	{
		if(vis[i]) prime[tot++] = i,d[i]=1;
		for(int j=0;j<tot&&i*prime[j]<=n;++j)
		{
			vis[i*prime[j]] = 0;
			if(i%prime[j]==0)
			{
				d[i*prime[j]] = d[i];
				break;
			}
			d[i*prime[j]] = d[i]+1; 
		}
	}
}
void solve()
{
	cin>>n;
	ll ans = 0;
	for(int i=1;i<=n;++i)
	{
//		cout<
		ans = (ans + 1ll*(n/i)*a[d[i]]%mod)%mod;
	}
	cout<<ans;
}
signed main(void)
{
	a[0] = 1;
	for(int i=1;i<=11;++i) a[i] = a[i-1] * 2 % mod;
	init(N-1);
//	for(int i=0;i<=100;++i) cout<
	solve();
	return 0;	
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48