Problem A (div 2)
照著它說的做就行了较性。
時(shí)間復(fù)雜度為
#include <iostream>
#include <algorithm>
using namespace std;
int w[4], h[4];
void Roll(int &w, int h0, int h1)
{
while(h0 >= h1)
{
w += h0;
h0--;
}
}
int main()
{
for(int i = 0; i < 3; i++)
{
cin >> w[i] >> h[i];
}
if(h[1] < h[2])
{
swap(w[1], w[2]);
swap(h[1], h[2]);
}
if(h[0] >= h[1])
{
Roll(w[0], h[0], h[1]);
w[0] -= w[1];
w[0] = max(0, w[0]);
h[0] = h[1] - 1;
}
if(h[0] >= h[2])
{
Roll(w[0], h[0], h[2]);
w[0] -= w[2];
w[0] = max(0, w[0]);
h[0] = h[2] - 1;
}
Roll(w[0], h[0], 0);
cout << w[0] << endl;
return 0;
}
Problem B (div 2)
事實(shí)上只需要搭出一個(gè)a*b的網(wǎng)格的左上角的邊（也就是a+b條邊）棱诱，那么便可以構(gòu)建出a*b個(gè)以內(nèi)的任意個(gè)數(shù)的正方形格子。
于是問題便變?yōu)椋o定n拐揭，求出最小的a+b使得a*b>=n
那么画饥，假設(shè)len=a+b岭皂，二分答案即可见擦。
時(shí)間復(fù)雜度為
#include <iostream>
#include <cmath>
using namespace std;
typedef long long LL;
bool check(LL len, LL n)
{
LL maxn = (len / 2) * (len - len / 2);
return maxn >= n;
}
int main()
{
LL n;
cin >> n;
LL l = 2, r = 2*n;
while(l < r)
{
LL mid = (l + r) >> 1;
if(check(mid, n))
{
r = mid;
}
else
{
l = mid + 1;
}
}
cout << l << endl;
return 0;
}
Problem C (div 2)
首先需要需要判斷是否是impossible摘完。當(dāng)最小長度大于k姥饰，或者最大長度小于k，那么認(rèn)為其為Impossible的孝治。
接著就是如何構(gòu)造出符合要求的串列粪。這個(gè)只需要貪心地盡可能用掉前面的*和?就行了。
時(shí)間復(fù)雜度為
#include <iostream>
#include <string>
#include <vector>
using namespace std;
#define INF 200000
string s;
vector<int> stat;
int Caclu_min()
{
int ret = 0;
for(int i = 0; i < s.length(); i++)
{
if(stat[i] == 0)
{
ret++;
}
}
return ret;
}
int Caclu_max()
{
int ret = 0;
for(int i = 0; i < s.length(); i++)
{
if(stat[i] == 2)
{
return INF;
}
ret++;
}
return ret;
}
string Solve(int k)
{
string ret;
if((k < Caclu_min()) || (k > Caclu_max()))
{
ret = "Impossible";
return ret;
}
int min_len = Caclu_min();
for(int i = 0; i < s.length(); i++)
{
if(stat[i] == 0)
{
ret += s[i];
}
else if(stat[i] == 1)
{
if(k > min_len)
{
ret += s[i];
k--;
}
}
else
{
while(k > min_len)
{
ret += s[i];
k--;
}
}
}
return ret;
}
int main()
{
string input_s;
cin >> input_s;
for(int i = 0; i < input_s.length(); i++)
{
if(input_s[i] == '?')
{
stat[s.length() - 1] = 1;
}
else if(input_s[i] == '*')
{
stat[s.length() - 1] = 2;
}
else
{
s += input_s[i];
stat.push_back(0);
}
}
int k;
cin >> k;
cout << Solve(k) << endl;
return 0;
}
Problem A (div 1)
這個(gè)事實(shí)上可以貪心地將每個(gè)點(diǎn)的權(quán)值安排在【不跟已知的沖突的情況下谈飒，點(diǎn)的權(quán)值分布盡可能往根部走】
于是就需要兩遍遍歷操作：
- 第一次遍歷從末尾往根部遍歷岂座，將所有未知的
全部換成其兒子們的所有已知的
- 第二次遍歷從根部往末尾遍歷并計(jì)算
。如果此時(shí)
來計(jì)算
注意判斷impossible的情況费什。
時(shí)間復(fù)雜度為
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
int p[100005];
int s[100005];
int a[100005];
vector<int> e[100005];
int main()
{
int n;
scanf("%d", &n);
for(int i = 2; i <= n; i++)
{
scanf("%d", &p[i]);
e[p[i]].push_back(i);
}
for(int i = 1; i <= n; i++)
{
scanf("%d", &s[i]);
}
bool flag = true;
for(int i = n; i >= 1; i--)
{
if(s[i] != -1)
{
for(int j = 0; j < e[i].size(); j++)
{
if(s[e[i][j]] == -1)
{
continue;
}
if(s[i] > s[e[i][j]])
{
flag = false;
break;
}
}
}
else
{
for(int j = 0; j < e[i].size(); j++)
{
if(s[i] == -1)
{
s[i] = s[e[i][j]];
}
else if(s[e[i][j]] != -1)
{
s[i] = min(s[i], s[e[i][j]]);
}
}
}
}
if(flag)
{
for(int i = 1; i <= n; i++)
{
if(s[i] == -1)
{
a[i] = 0;
s[i] = s[p[i]];
}
else
{
if(s[i] < s[p[i]])
{
flag = false;
break;
}
a[i] = s[i] - s[p[i]];
}
}
}
if(flag)
{
LL ans = 0;
for(int i = 1; i <= n; i++)
{
ans += a[i];
}
printf("%lld\n", ans);
}
else
{
printf("-1\n");
}
return 0;
}
