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'\))。
标签:一个点,10.25,报告,--,long,后继,int,解题,ans From: https://www.cnblogs.com/wapmhac/p/16827655.html