2017-2018 ACM-ICPC Asia East Continent League Final (ECL-Final)
9題金
6題銀
5題銅
題目比較簡單，但是讀題太難了…
比賽鏈接：https://codeforces.com/gym/101775
最近時間比較緊，簡單寫一點題解吧，還有好多題沒有補嗚嗚嗚
這場讀題太難了…
最后三題過的人太少了懶得補了…
目錄
- A、Chat Group
- B、Scapegoat
- C、Traffic Light
- D、Mr. Panda and Geometric Sequence
- J、Straight Master
- H、Mr. Panda and Birthday Song
- K、Downgrade
- L、SOS
- M、World Cup
A、Chat Group
簽到題
題目要求的是 C n k + ? + c n n C_n^k+\cdots+c_n^n Cnk?+?+cnn?，
但是 n ≤ 1 0 9 n\le 10^9 n≤109不直接列舉或者預處理，所以考慮反著做，
我們知道 C n 1 + C n 2 + ? + C n n = 2 n C_n^1+C_n^2+\cdots+C_n^n=2^n Cn1?+Cn2?+?+Cnn?=2n，所以答案就是 2 n ? ( C n 0 + C n 1 + ? + C n k ? 1 ) 2^n-(C_n^0+C_n^1+\cdots+C_n^{k-1}) 2n?(Cn0?+Cn1?+?+Cnk?1?)
k ≤ 1 0 5 k\le 10^5 k≤105 可以遞推求組合數，因為要求的是 C n 0 ～ C n k ? 1 C_n^0\sim C_n^{k-1} Cn0?～Cnk?1?，所以我們可以直接遞推求組合數，從 C n 0 = 1 C_n^0=1 Cn0?=1 開始， C n m = n ? m + 1 m × C n m ? 1 C_n^m=\cfrac{n-m+1}{m}\times C_n^{m-1} Cnm?=mn?m+1?×Cnm?1?，
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
using namespace std;
typedef long long ll;
const int N = 500007, mod = 1e9 + 7;
const double PI = acos(-1);
int n, m, t, k, kcase;
int qpow(int a, int b)
{
int res = 1;
while(b) {
if(b & 1) res = 1ll * res * a % mod;
a = 1ll * a * a % mod;
b >>= 1;
}
return res;
}
int inv(int x)
{
return qpow(x, mod - 2);
}
int main()
{
scanf("%d", &t);
while(t -- ) {
scanf("%d%d", &n, &k);
if(k > n) {printf("Case #%d: 0\n", ++ kcase);continue;}
ll ans = qpow(2, n) - 1;
ll sum = 1;
for(int i = 1; i <= k - 1; ++ i) {
sum = 1ll * sum * 1ll * (n - i + 1) % mod * inv(i) % mod;
ans = (ans - 1ll * sum % mod + mod) % mod;
}
printf("Case #%d: %lld\n", ++ kcase, ans);
}
return 0;
}
B、Scapegoat
Problem
現在某人闖禍了，產生了 N 個鍋，每個鍋有個嚴重點數，現在可以安排 M 個替罪羊去背鍋，
每個替罪羊最多只能背一個鍋，若一只羊背一個鍋，則該鍋的嚴重點數全部算在它頭上；若多只羊背同一個鍋，則每個羊分到該鍋的一部分的嚴重點數，
現在考慮一種安排方案，使得所有的身上的嚴重點數的方差最小，
Solution
先考慮上 N 只羊一一對應地背 N 個鍋，剩下 M?N 個替罪羊身上嚴重點數均為 0，當然這樣并不是最優解，
應當把再剩下 M?N 個替罪羊安排進 N 個鍋里分攤責任，使得方差減小，考慮貪心的思路，每次安排進去一只羊，都要使得方差減小最多，
考慮將新來的羊安排到某個任務，該任務嚴重點數為 a[i]，且原來的背鍋羊數是 num，那么首先每個替罪羊分到的嚴重點數的平均數肯定是不變的 X ￣ = a [ 1 ] + a [ 2 ] + ? + a [ n ] m \overline{X} = \cfrac{a[1]+ a[2]+ \cdots + a[n]}{m} X=ma[1]+a[2]+?+a[n]?，，因此它原本對方差的貢獻為 1 m ? n u m ? ( a [ i ] n u m ? X ￣ ) 2 \cfrac{1}{m} \cdot num \cdot (\cfrac{a[i]}{num}-\overline{X})^2 m1??num?(numa[i]??X)2，
而現在新加進去一個替罪羊，這個任務對方差的新的貢獻為 1 m ? ( n u m + 1 ) ? ( a [ i ] n u m + 1 ? X ￣ ) 2 \cfrac{1}{m} \cdot (num+1) \cdot (\cfrac{a[i]}{num+1}-\overline{X})^2 m1??(num+1)?(num+1a[i]??X)2
顯然，關鍵的差值就是 Δ = n u m ? ( a [ i ] n u m ? X ￣ ) 2 ? ( n u m + 1 ) ? ( a [ i ] n u m + 1 ? X ￣ ) 2 = a [ i ] 2 n u m ? ( n u m + 1 ) ? X ￣ 2 \Delta = num \cdot (\cfrac{a[i]}{num}-\overline{X})^2 -(num+1) \cdot (\cfrac{a[i]}{num+1}-\overline{X})^2 = \cfrac{a[i]^2}{num \cdot (num+1)} - \overline{X}^2 Δ=num?(numa[i]??X)2?(num+1)?(num+1a[i]??X)2=num?(num+1)a[i]2??X2，因此我們讓每次挑一個任務讓它的 Δ + X ￣ 2 = a [ i ] 2 n u m ? ( n u m + 1 ) \Delta + \overline{X}^2 = \cfrac{a[i]^2}{num \cdot (num+1)} Δ+X2=num?(num+1)a[i]2? 最大即可，直接使用優先佇列維護即可，
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
#include <queue>
using namespace std;
typedef long long ll;
typedef int itn;
const int N = 500007, mod = 1e9 + 7;
const double PI = acos(-1);
const double eps = 1e-8;
int n, m, a[N], t;
int sum, kcase;
double avg;
struct node
{
itn id, num;
node(int _id, int _num) {id = _id, num = _num;}
double calc() const {
return a[id] *a[id] * 1.0 / num / (num + 1);
}
bool operator < (const node& t) const
{
return this->calc() < t.calc() + eps;
}
};
priority_queue<node> q;
int main()
{
scanf("%d", &t);
while(t -- ) {
scanf("%d%d", &n, &m);
double avg = 0;
for (int i = 1; i <= n; ++ i) {
scanf("%d", &a[i]);
avg += a[i];
q.push(node(i, 1));
}
avg /= m;
for (int i = 1; i <= m - n; ++ i) {
node t = q.top();
q.pop();
q.push(node(t.id, t.num + 1));
}
double ans = 0;
while(q.size()) {
node t = q.top();
q.pop();
ans += (double)t.num * ((double)a[t.id] / t.num - avg) * ((double)a[t.id] / t.num - avg);
}
ans /= m;
printf("Case #%d: %.9f\n", ++ kcase, ans);
}
return 0;
}
C、Traffic Light
閱讀理解題，
“他本來可以通過修改一路遇到的全是綠燈，但是他偏要給自己找麻煩，偏要遇到一個最壞的情況，等滿時間最長的紅燈”
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
using namespace std;
typedef long long ll;
typedef int itn;
const int N = 500007, mod = 1e9 + 7;
const double PI = acos(-1);
int n, m, t, kcase;
double maxx;
int main()
{
scanf("%d", &t);
while(t -- ) {
maxx = 0;
scanf("%d", &n);
double sum = 0;
for(int i = 0; i <= n; ++ i) {
double x;
scanf("%lf", &x);
sum += (double)x;
}
for(int i = 1; i <= n; ++ i) {
double x, y;
scanf("%lf%lf", &x, &y);
maxx = max(maxx, y);
}
sum += (double)maxx;
printf("Case #%d: %.8f\n", ++ kcase, sum);
}
return 0;
}
D、Mr. Panda and Geometric Sequence
Problem
定義happy number, 可以將數字分為三個及以上的整數，且三個整數為公比 >1 的等比數列，
詢問l-r范圍記憶體在多少 happynumber
Solution
可以證明，分解后的等比數列第二項是小于 1 e 5 1e5 1e5 的，
簡要證明如下：
對于每個數字 x x x ，其位數是 ? l o g 10 x ? + 1 \lfloor log_{10}x \rfloor+1 ?log10?x?+1,若將 y y y 與 x x x 拼接到一起，則其結果為 y × 1 0 ? l o g 10 x ? + 1 y\times 10^{\lfloor log_{10}x \rfloor+1} y×10?log10?x?+1 顯然 y × 1 0 ? l o g 10 x ? + 1 + x > splice ( x , y ) y\times 10^{\lfloor log_{10}x \rfloor+1}+x>\text{splice}(x,y) y×10?log10?x?+1+x>splice(x,y) (注： splice ( x , y ) \text{splice}(x,y) splice(x,y) 為直接將 x y xy xy 拼接) ，
以推廣， splice ( a 0 , a 1 . . . a n ) > a 0 a 1 . . . a n \text{splice}(a_0,a_1...a_n) > a_0a_1...a_n splice(a0?,a1?...an?)>a0?a1?...an? ，在最壞情況下，即數列由三項組成且總長度為 15 15 15 此時存在 a 0 a 1 a 2 < splice ( a 0 , a 1 , a 2 ) < = 1 0 15 a_0a_1a_2< \text{splice}(a_0,a_1,a_2)<=10^{15} a0?a1?a2?<splice(a0?,a1?,a2?)<=1015
設等比數列公比為 q q q ，則存在 a 0 3 q 3 < 1 0 1 5 {a_0}^3q^3 <10^15 a0?3q3<1015，即： a 0 q < 1 0 5 , a 1 < 1 0 5 a_0q<10^5,a_1<10^5 a0?q<105,a1?<105
此時我們只要在列舉首項和公比即可,設
a
0
=
k
×
p
×
p
,
a
1
=
k
×
p
×
q
,
a
2
=
k
×
q
×
q
a_0=k\times p\times p,a_1=k\times p\times q,a_2=k\times q\times q
a0?=k×p×p,a1?=k×p×q,a2?=k×q×q,此時公比為
q
p
\cfrac{q}{p}
pq? （
p
,
q
p,q
p,q 必須為最簡分數）,一直列舉下一項直到
a
n
?
1
m
o
d
??
p
>
0
a_{n-1} \mod p > 0
an?1?modp>0 或總長度大于 1e15 即可，
預處理出所有happynumber, 接下來二分查詢即可，
復雜度在 O ( 1 e 5 × l o g 2 + T ? ( l o g ( 2 e 6 ) ) O(1e5\times log^2+T*(log(2e6)) O(1e5×log2+T?(log(2e6))
code
#include <bits/stdc++.h>
#define reg register
#define ios ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int inf = 0x3f3f3f3f;
const double eps = 1e-10;
const int maxn = 2e5 + 10;
const double pi = acos(-1.0);
const ll mod = 1e9 + 7;
vector<ll> res;
int lg(ll x) //求x的位數
{
int res = 0;
while(x) res++,x/=10;
return res;
}
ll splice(ll a, ll b) //拼接字串
{
if(lg(a) + lg(b) > 15) return 1e17;
ll tmp = b, base = 1;
while(tmp) base*=10,tmp/=10;
a = a * base + b;
return a;
}
void init()
{
for(ll p = 1;p <= 1e5;++p){
for(ll q = p + 1;p * q <= 1e5;++q){
if(__gcd(p,q) > 1) continue;
for(ll k = 1;p * q * k <= 1e5;++k){
ll x, y, z;
x = k * p * p;
y = k * p * q;
z = k * q * q;
ll num = splice(x,splice(y,z));
res.push_back(num);
ll now = z;
while(1){
if(now % p) break;
now /= p;
now *= q;
num = splice(num,now);
if(lg(num) > 15) break;
res.push_back(num);
}
}
}
}
sort(res.begin(),res.end());
}
inline int slove(ll x)
{
return upper_bound(res.begin(),res.end(),x) - res.begin();
}
int main()
{
ios;
int cas = 0;
init();
printf("%d\n",res.size());
int t;
cin>>t;
while(t--){
ll l,r;
cin>>l>>r;
printf("Case #%d: %d\n",++cas, slove(r) - slove(l-1));
}
return 0;
}
J、Straight Master
顯然這種題目要用差分來做，簡單特判一下就行了，
求出來差分陣列以后，如果有 + x +x +x，它的右邊 5 5 5 格以內有 ? x -x ?x 顯然可以區間消為 0 0 0，如果沒有的話，可以送給它右邊 5 5 5 格以內的一個整數
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main()
{
ll t;
ll cs = 0;
scanf("%lld",&t);
while(t--){
ll n;
scanf("%lld",&n);
vector<ll> a(n + 2,0), res(n + 2);
for (ll i = 1; i <= n;++i)
scanf("%lld",&a[i]);
for (ll i = 1; i <= n+1;++i){
res[i] = a[i] - a[i - 1];
}
bool ok = true;
for (ll i = 1; i <= n+1;++i){
if(res[i] < 0){
ok = false;
break;
}
if(res[i]){
for (ll j = i + 3; j <= i + 5 && j <= n+1&&res[i]>0;++j){
ll tmp = res[j];
if(tmp < 0){
if(-tmp>=res[i]){
tmp += res[i];
res[i] = 0;
}
else{
res[i] += tmp;
tmp = 0;
}
}
res[j] = tmp;
}
if(res[i]>0){
int x = i + 3;
if(x+3 <= n+1){
res[x] += res[i];
res[i] = 0;
}
else if(x<=n+1){
res[n + 1] += res[i];
res[i] = 0;
}
}
}
}
if(ok)
printf("Case #%lld: Yes\n",++cs);
else
printf("Case #%lld: No\n",++cs);
}
}
H、Mr. Panda and Birthday Song
待更…
K、Downgrade
隊友寫的
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
long long l[maxn];
long long sum[maxn];
template<typename T>
inline T read(T &x)
{
x = 0;
long long f = 1;
char c;
while(!isdigit(c = getchar())) if(c == '-')
f = -1;
while(isdigit(c)){
x = (x << 1) + (x << 3) + (c ^ 48);
c = getchar();
}
return x * f;
}
int main()
{
int cas = 0;
int t;
read(t);
while(t--){
long long a, b, n;
read(a), read(b), read(n);
for (int i = 1; i <= a;++i){
read(l[i]);
sum[i] = sum[i - 1] + l[i];
}
long long la = a, lb = b;
int pos = a;
while(n--){
long long tmp = a;
while(sum[pos-1] >= a)
pos--;
a = pos;
b = tmp - sum[a - 1];
if(la == a && lb == b)
break;
la = a, lb = b;
}
printf("Case #%d: %lld-%lld\n",++cas, a, b);
}
return 0;
}
L、SOS
我花了半個小時硬推出來的，把對手逼到必敗態就行了，必勝態就是組成 S _ _ S S\_\_\ S S__ S 的局面即可， 7 = 3 + 1 + 3 7=3+1+3 7=3+1+3 ，
具體可以看這個大佬寫的題解，跟我的思路差不多https://www.cnblogs.com/fan-jiaming/p/9568741.html
注意最后 16 16 16 是因為長度至少為 16 16 16 的話，不管先手怎么下，哪怕在中間放一個 O O O ，兩邊總會留有超過 7 7 7 格的空格給對手，這樣后手變成了先手，而先手， 7 7 7 格必勝，
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
using namespace std;
typedef long long ll;
typedef int itn;
const int N = 500007, mod = 1e9 + 7;
const double PI = acos(-1);
int n, m, t;
int kcase;
int main()
{
scanf("%d", &t);
while(t -- ) {
scanf("%d", &n);
if((n & 1) && n >= 7) {
printf("Case #%d: Panda\n", ++ kcase);
}
else if(((n & 1) == 0) && n >= 16) {
printf("Case #%d: Sheep\n", ++ kcase);
}
else printf("Case #%d: Draw\n", ++ kcase);
}
return 0;
}
本來想打表，不會寫自閉地硬推了半個小時…，賽后搜大佬的題解的打表程式學習一下：
#define FRER() freopen("i.txt","r",stdin)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f;
const unsigned int M=1e9+9e8;
const int N=100;
int a[N],n,cnt;
char mp[M];
unsigned int state()
{
unsigned int ret=0;
for(int i=0; i<n; ++i)
ret=(ret<<1)+ret+a[i];
return ret<M?ret:ret%M;
}
bool check()
{
for(int i=0; i+2<n; ++i)
if(a[i]==1&&a[i+1]==2&&a[i+2]==1)return true;
return false;
}
int dfs()
{
if(check())return -1;
if(cnt>=n)return 0;
unsigned st=state();
if(mp[st]^INF)return mp[st];
bool flag=false;
for(int i=0; i<n; ++i)
{
if(a[i])continue;
for(int j=1; j<=2; ++j)
{
a[i]=j;
cnt++;
int t=dfs();
if(!~t)
{
cnt--;
a[i]=0;
return mp[st]=1;
}
if(!t)flag=true;
cnt--;
a[i]=0;
}
}
return mp[st]=(flag?0:-1);
}
int main()
{
//FRER();
for(n=1; ; ++n)
{
memset(mp,INF,sizeof mp);
memset(a,0,sizeof a);
cnt=0;
printf("%d %d\n",n,dfs());
}
return 0;
}
M、World Cup
隊友寫的
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
int cs = 0;
scanf("%d",&t);
while(t--){
vector<int> num({48, 56, 60, 62, 63});
vector<int> val(5);
for (int i = 0; i < 5;++i)
scanf("%d",&val[i]);
int n;
scanf("%d",&n);
vector<int> a(n + 1);
for (int i = 1; i <= n;++i)
scanf("%d",&a[i]);
sort(a.begin()+1,a.end());
using ll = long long;
int now = 0;
ll sum = 0;
for (int i = 1; i <= n;++i){
while(num[now] < a[i])
now++;
if(a[i] <= num[now]){
sum += val[now];
}
}
sum *= 10000;
printf("Case #%d: %lld\n",++cs,sum);
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/267440.html
標籤：其他
下一篇：LDU20級新生排位賽第二場