A.DZY Loves Hash

　　hash函數(shù) h(x) = x % p　　輸出第一次沖突的位置

#include<iostream> #include<cstdio> #include<cstdlib>using namespace std;const int maxn = 4000;int p, n; bool inhash[maxn];int main() {freopen("447A.in", "r", stdin);cin >> p >> n;for(int i = 0; i < n; i++) {long long t;cin >> t;if(!inhash[t % p]) inhash[t % p] = 1;else {cout << i+1 << endl;return 0;}}cout << -1 << endl;return 0; }

　　

　　B.DZY Loves Strings

　　　　對(duì)于一個(gè)字符串,每個(gè)字母有相應(yīng)的權(quán)值,由這個(gè)公式計(jì)算f(s)

?

現(xiàn)在能夠插入k個(gè)任意字母,要求使得新的字符串f(s')值最大

　　字符串就是幌子,替換成數(shù)字,插入的字符很明顯貪心一下取最大的,一開始也沒發(fā)現(xiàn)規(guī)律,瞎搞的,題解的意思大概是:

　　插入x到位置p之后,則增加的權(quán)值為x*p+Ws(p+1)+Ws(p+2)...(p以后每一個(gè)權(quán)值) -> x+x+x+x...+Ws(p+1)+Ws(p+2)...容易觀察到其實(shí)是用x替換前p個(gè)Ws,而由于貪心策略,x >= Ws.所以上式要取最大,p應(yīng)該取|s|,對(duì)于剩下k-1個(gè)x同理,最終轉(zhuǎn)化為把p個(gè)x插入到最后端得到的f(s‘)

(這份代碼沒刪除之前亂搞的部分,比較亂就不貼了)

(B都寫不來。。。這絕壁回家養(yǎng)豬節(jié)奏！)

?

　　C.DZY Loves Sequences

　　咋一眼看像是dp,可是自己死活想不出來思路,O(N),結(jié)果是自己沒自習(xí)審題,ai, ai+1, ai+2 連續(xù)的!

　　大意是給你一個(gè)數(shù)列,最多修改一個(gè)數(shù)字,球得最長(zhǎng)的單調(diào)遞增子串(嚴(yán)格的)(連續(xù)的!!!)

　　可以設(shè)想一下如果x是要修改的數(shù)字,a[x+1]-a[x-1]>1(因?yàn)槭钦麛?shù),嚴(yán)格單調(diào)),以x為界左邊是一個(gè)以a[x-1]為尾的單調(diào)增,右邊是a[x+1]為首單調(diào)增,我們可以預(yù)處理出這兩邊的長(zhǎng)度,然后枚舉每一個(gè)a[i](2~n-1),取max即可

　　預(yù)處理過程就算是簡(jiǎn)單dp吧...以從左往右為例 f[i] = 1 (a[i] <= a[i-1])　 或 f[i-1]+1 (a[i] > a[i-1])　

?

(審題吶!英文不好容易漏細(xì)節(jié)...)

　　

#include <iostream> #include <cstdlib> #include <cstdio>using namespace std;const int maxn = 100000+50;int n; int a[maxn], r[maxn], l[maxn], f[maxn];int main() {scanf("%d", &n);for(int i = 1; i <= n; i++)scanf("%d", a+i);for(int i = 1; i <= n; i++)f[i] = 1;l[1] = 1;for(int i = 2; i <= n; i++)l[i] = (a[i] > a[i-1]? l[i-1]+1: 1);r[n] = 1;for(int i = n-1; i >= 1; i--)r[i] = (a[i] < a[i+1]? r[i+1]+1: 1);for(int i = 1; i <= n; i++) {if(i >= 2) f[i] = max(f[i], 1+l[i-1]);if(i <= n-1) f[i] = max(f[i], 1+r[i+1]);if(a[i+1] - a[i-1] > 1) f[i] = max(f[i], 1+r[i+1]+l[i-1]);}int ans = 0;for(int i = 1; i <= n; i++)ans = max(ans, f[i]);printf("%d\n", ans); return 0; }

?

　　

轉(zhuǎn)載于:https://www.cnblogs.com/gemmeg/p/3854371.html

總結(jié)

以上是生活随笔為你收集整理的Codeforces Round #FF的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。