Problem 1: 魔法陣~
時間限制:1000MS
記憶體限制:128000KB
思路：
由于要求洗掉后仍然是一個正多邊形，
這就保證剩余的點數一定是n的因子，
只有這樣才能均勻洗掉，
所以我們只需要列舉n的因子作為剩余多邊形的頂點數，
對答案取max即可，
一個數的因子數個數是log級別的，
而且每次選擇魔法陣的時候每個點
只屬于當前因子的某一個魔法陣，
所以每個點只訪問一次，
所以總復雜度為
O
(
n
log
?
n
)
O(n\log n)
O(nlogn)，
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <ctime>
#include <cctype>
#include <bitset>
#include <utility>
#include <sstream>
#include <complex>
#include <iomanip>
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
int n,t[20010],yz[20010],sum,ct;
void ys(int x)
{
for(int i = 2; i < x; i++)
if(!(x % i))
yz[ct++] = i;
}
int main()
{
cin>>n;
for(int i = 1; i <= n; i++)
{
cin>>t[i], sum += t[i];
}
ys(n);
if(n == 3 || !ct) {cout<<sum<<endl; return 0;}
for(int i = 0; i < ct; i++)
{
int gs = yz[i], begin = 1;
while(gs--)
{
int tot = 0,cnt = 0;
for(int j = begin; j <= n; j += yz[i]) tot += t[j], cnt++;
if(cnt >= 3) sum = max(sum, tot);
begin++;
}
}
printf("%d\n", sum);
return 0;
}
Problem 2: 小biu放牛
時間限制:1000MS
記憶體限制:128000KB
PS:題目的輸出格式不要管他，什么碼頭都來了！
思路：
二分+貪心，我們要貪心把牛放在最前面，
那么牛頭的位置就是i-t-x;但是題目要求不能重疊，
用max比較一下可以確定牛頭的位置在哪，這樣保證了靠前，
然后我們可以用頭部的位置，判斷是否越界，
最后要判斷一下尾部有沒有越界,
時間復雜度為
O
(
n
log
?
n
)
O(n\log n)
O(nlogn)；
#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
const int N=5e4+10;
int a[N];
int n, x, m;
bool check(int mid)
{
int h=0, t=0;
for(int i = 1; i <= n; i++)
{
h = max(t, a[i] - mid - x);
if(abs(h - a[i] + x) > mid) return false;
t = h + 2 * x;
if(t > m) return false;
}
return true;
}
int main()
{
scanf("%d%d%d", &n, &x, &m);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
int l = 0, r = m;
while(l <= r)
{
int mid = l + r >> 1;
if(check(mid)) r = mid - 1;
else l = mid + 1;
}
if(l > m) printf("-1\n");
else printf("%d\n", l);
}
/*
3 2 16
1
3
14
*/
Problem 3: 小A的游戲
時間限制:1000MS
記憶體限制:256000KB
（為什么我覺得這道題比前兩道還水？）
思路：
考慮如果出現兩個相同字符之間的距離小于等于k時，
小A一定可以洗掉這連續的一段，讓小B無法判斷他
洗掉的是前面的字符還是后面的字符，否則則小B一定能判斷，
所以當且僅當出現兩個相同字符之間的距離小于等于k時，
答案為Uncertain，否則答案為Certain，
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
int t, k, last[30];
bool flag;
string s;
int main()
{
scanf("%d", &t);
while(t--)
{
memset(last, -1, sizeof(last)), flag=0;
cin>>s;
scanf("%d", &k);
int l = s.size();
if(k == l) {printf("Certain\n"); continue;}
else
{
for(int i = 0; i < l; i++)
{
if(last[s[i] - 'a'] != -1 && i - last[s[i] - 'a'] <= k)
{printf("Uncertain\n"), flag=1; break;}
last[s[i] - 'a'] = i;
}
}
if(!flag) printf("Certain\n");
}
return 0;
}
/*
1
snuke
2
*/
Problem 4: 小Biu闖關
時間限制:1000MS
記憶體限制:128000KB
思路：
首先，必須承認考場爆零了，
0分暴力：
考慮一個區間[A,B],能表達的數為[A2,B2], [A3,B3]…[AK,BK].
那么我們無腦地去K,直到A*K>Y為止，
考慮任意一個區間的最大貢獻，肯定是為：
m
i
n
(
y
,
k
?
1
l
l
?
b
)
?
m
a
x
(
x
,
k
?
1
l
l
?
a
)
+
1
min(y, k * 1ll * b) - max(x, k * 1ll * a) + 1
min(y,k?1ll?b)?max(x,k?1ll?a)+1
用個ans將這K個區間的貢獻加個總，輸出即可，
但是絕對會爆零！！！
100分
我們想想，難道一定要到AK>Y為止，
肯定不是了，當kA<=(k-1)*B時，區間就發生重合，
之后的數就全部都能湊出來，
那我們改結束條件為這個，就歐了！！！
#include <cstdio>
#include <iostream>
#define ll long long
using namespace std;
int t;
ll a, b, x, y;
int main()
{
scanf("%d", &t);
while(t--)
{
ll ans = 0;
scanf("%lld%lld%lld%lld", &a, &b, &x, &y);
ll begin = (b < x? x / b + 1: 1);
for(ll k = begin; k; k++)
{
ll l = a * k, r = b * k, nl = a * (k + 1);
if(l > y) break;
if(nl <= r) {ans += (y - max(l, x) + 1); break;}
ans += (min(y, r) - max(x, l) + 1);
}
printf("%lld\n", ans);
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/195269.html
標籤：其他
下一篇：漫漫秋招路