10.25 解题报告

T1

用时：1.5h

赛时 \(30\) min切了，对着错大样例调了 \(1\) h。

#include<bits/stdc++.h>
#define ll long long
#define int long long
//#define ull unsigned long long
#define lc(k) k<<1
#define rc(k) k<<1|1
#define lb lower_bound
#define orz cout<<"gzn ak ioi\n"
const int MAX=1e6+10;
const int MOD=1e9+7;
using namespace std;
inline char readchar() {
	static char buf[100000], *p1 = buf, *p2 = buf;
	return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline int read() {
#define readchar getchar
	int res = 0, f = 0;
	char ch = readchar();
	for(; !isdigit(ch); ch = readchar()) if(ch == '-') f = 1;
	for(; isdigit(ch);ch = readchar()) res = (res << 1) + (res << 3) + (ch ^ '0');
	return f ? -res : res;
}
inline void write(int x) {
    if(x<0){putchar('-');x=-x;}
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
/*
一圈一圈的增长
紧挨着增长
第一圈:1
2      6
3      12
4      18
5      24
第n圈有(n-1)*6个方块 n>1
第一圈有 1 个

假设当前数目恰好可以铺满n圈 

1+\sum_{i=2}^n 6(n-1)=1+6(1+n-1)(n-1)/2=1+3n(n-1)

考虑第n+1圈剩了k个
每完全空出一条边答案减少1，第一条边需要少n+1个，2-5是n个
6是n-1个

做完了 
*/
signed main(){
	freopen("square.in","r",stdin);
	freopen("square.out","w",stdout);
	int x=read(),ans=0;
	int n=(3.0+sqrt(9.0+12.0*x-12.0))/6.0;
	int sum=3*n*(n-1)+1;//整圈的个数 
	ans=6*(n+1); 
	int k=x-sum,t=6*n;
	if(t-k>=n+1){//6
		ans--,t-=(n+1);
		if(t-k>=n){//5 
			ans--,t-=n;
			if(t-k>=n){//4
				ans--,t-=n;
				if(t-k>=n){//3
					ans--,t-=n;
					if(t-k>=n){//2
						ans--,t-=n;
						if(t-k>=n-1){
							ans--;t-=(n-1);
						}
					}
				}
			}
		}
	}
	cout<<ans;
	return 0; 
}

T2

用时： \(30\) min
期望得分：\(0\)
实际得分：\(10\)

得了十分是因为对于 \(f_i=i\) 的点，我的贪心恰好是对的。

考场弃掉是因为觉得自己读不懂题目，实际上确实是没读对题，题目中 \(i\) 号位置为空是指的真的被取空，而不是按下了 \(a_i\) 次按钮。

考虑对于每一个点 \(i\)，我们由它的 \(f_i\) 向他连一条边，表示 \(f_i\) 可由 \(i\) 买到，但实际上对于 \(f_i\)，一定是只用花费最小的点来买它，所以只记录一下它的后继里面 \(c\) 值最小的即可。

不难发现，由于每个点的出度最多是 \(1\)（最多只用一个点来买它），入度也最多是 \(1\)（最多只能买一个点），所以这个图是由若干条链和若干个简单环组成的。

环链之间相互独立，于是对每一条链和每一个环可以单独考虑。

对于链，叶子结点没有出度，贡献为 \(0\)，其他的贡献都是后继的 \(c\) 减去这个节点的 \(d\) 再乘上再乘上 \(a\)。

对于链，一定有一个点贡献为 \(0\)，考虑这个点应该是哪个。

现在先假设 \(i\) 号点的贡献为 \(0\)，假设它的后继是 \(v\)，那么它对于没断开之前的贡献就减少了 \(c_v-d_i\)，于是要找到 \(c_v-d_i\) 最小的点，将其贡献减去。

但这是不对的，因为一个点虽然只记录了一个后继，但是他可能还有收益次大的后继，这个后继的贡献也是应该算上的，假设这个节点是 \(v'\)，那么删掉一个点的 \(\Delta=-(c_v-d_i)+c_{v'}-d_i=c_{v'}-c_v\)，所以应当找到 \(c_{v'}-c_v\) 最小的点（前提是存在 \(v'\)）。