“蔚来杯“2022牛客暑期多校训练营5（GBKFH）

本文没有正经题解 只有：
$rnm$ 退钱

G-KFC Crazy Thursday

$PAM$ 模板题，属于改改就能过

#include using namespace std;
const int MAXN = 2e6 + 5;struct Node {Node *ch[26], *fail;int len, sum;
} tr[MAXN];int n;
char s[MAXN];
int ncnt = 2;
Node* last;Node* New(int len) {tr[ncnt].len = len;tr[ncnt].fail = &tr[0];for (int i = 0; i < 26; i++)tr[ncnt].ch[i] = &tr[0];return &tr[ncnt++];
}Node* GetFail(Node* x, int pos) {while (s[pos - x->len - 1] != s[pos])x = x->fail;return x;
}void Init() {tr[0].len = 0;tr[1].len = -1;tr[0].fail = &tr[1];tr[1].fail = &tr[0];for (int i = 0; i < 26; i++)tr[0].ch[i] = tr[1].ch[i] = &tr[0];last = &tr[0];
}void Insert(int pos) {Node* cur = GetFail(last, pos);if (cur->ch[s[pos] - 'a'] == &tr[0]) {Node* now = New(cur->len + 2);now->fail = GetFail(cur->fail, pos)->ch[s[pos] - 'a'];now->sum = now->fail->sum + 1;cur->ch[s[pos] - 'a'] = now;}last = cur->ch[s[pos] - 'a'];
}signed main() {cin >> n;cin >> s + 1;int k = 0;Init();int a = 0, b = 0, c = 0;for (int i = 1; i <= n; i++) {Insert(i);if (s[i] == 'k') {a += last->sum;}else if (s[i] == 'f') {b += last->sum;}else if (s[i] == 'c') {c += last->sum;}k = last->sum;}cout << a << " " << b << " " << c << endl;return 0;
}

B-Watches

二分操作次数，排序后贪心即可。

#include
using namespace std;
const int mod=1e9+7;
const int N=2e5+7;
typedef long long ll;
#define endl '\n'
#define int long long
#define PA pair<int,int>
int a[N],tmp[N];
int n,m;
bool check(int mid){int sum=0;for(int i=1;i<=n;i++)tmp[i]=a[i]+i*mid;sort(tmp+1,tmp+1+n);for(int i=1;i<=mid;i++){sum+=tmp[i];}return m>=sum;
}
void solve(){cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];int l=0,r=n+1,mid;while(l<r){mid=(l+r)/2;if(check(mid)){l=mid+1;}else r=mid;}cout<<l-1<<endl; 
}
signed main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t=1;//cin>>t;while(t--)solve();
}

K-Headphones

经典题面比代码难理解。

#include
#define maxn 200005
#define int long long
using namespace std;
int a[maxn],b[maxn];
char s[maxn];
int n,m;
int dp[maxn],sum1[maxn],sum2[maxn];
void solve(){scanf("%d%d",&n,&m);if(m>(n-1)/2){puts("-1");return ;}int rest=n-m;printf("%d\n",rest+m+1);
}signed main(){int t=1;//cin>>t;while(t--)solve();return 0;
}

F-A Stack of CDs

原题链接

冲进去扒一篇题解，把输入顺序 $r,x,y$ 更改为 $x,y,r$ ，再改个精度就过了

H-Cutting Papers

万能群友公式：

#include 
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);int main() {int n;cin >> n;printf("%.12lf\n", (double)n * n * 3.0 / 4 + n * PI / 4 - n / 2.0);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！