https://www.cnblogs.com/31415926535x/p/11460682.html
上午沒課,做一套題,,練一下手感和思維,,教育場的71 ,,前兩到沒啥,,後面就做的磕磕巴巴的,,,有想法但是不敢實作,,自我否定,,沒了思路就隻能官方題解,,發現其實都很簡單,,,思維場把,,,,
A There Are Two Types Of Burgers
貪心就完事了,,推出公式不知道怎麼證明是最優的,,,(敲錯變量還wale一發emmm
#include <bits/stdc++.h>
#define aaa cout<<233<<endl;
#define endl '\n'
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
// mt19937 rnd(time(0));
const int inf = 0x3f3f3f3f;//1061109567 > 1e9
const ll linf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-7;
const double pi = 3.14159265358979;
const int maxn = 1e5 + 5;
const int maxm = 1e3 + 5;
const int mod = 1e9 + 7;
int main()
{
// double pp = clock();
// freopen("233.in", "r", stdin);
// freopen("233.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t; cin >> t;
while(t--)
{
int b, p, f;
cin >> b >> p >> f;
int h, c;
cin >> h >> c;
int ans = 0;
if(h < c)
{
ans = c * (min(f, b / 2));
b -= 2 * min(f, b / 2);
ans += h * (min(p, b / 2));
}
else
{
ans = h * min(p, b / 2);
b -= 2 * min(p, b / 2);
ans += c * min(f, b / 2);
}
cout << ans << endl;
}
// cout << endl << (clock() - pp) / CLOCKS_PER_SEC << endl;
return 0;
}
B Square Filling
題意就是給你一個矩形,,由0,1組成,然後一次可以進行一個操作:把 \((x, y), (x, y + 1), (x + 1, y), (x + 1, y + 1)\) 這幾個點變成1,,然後問你從一個全零的矩陣變成這個矩陣的操作方法,,沒限制操作次數,,那就亂搞就行了,,
#include <bits/stdc++.h>
#define aaa cout<<233<<endl;
#define endl '\n'
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
// mt19937 rnd(time(0));
const int inf = 0x3f3f3f3f;//1061109567 > 1e9
const ll linf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-7;
const double pi = 3.14159265358979;
const int maxn = 1e3 + 5;
const int maxm = 1e3 + 5;
const int mod = 1e9 + 7;
int a[maxn][maxn];
vector<pair<int, int> > ans;
bool check(int x, int y)
{
if(a[x][y] && a[x][y + 1] && a[x + 1][y] && a[x + 1][y + 1])return true;
return false;
}
int main()
{
// double pp = clock();
// freopen("233.in", "r", stdin);
// freopen("233.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int n, m;cin >> n >> m;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
cin >> a[i][j];
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= m; ++j)
{
if(!a[i][j])continue;
if(check(i, j))ans.push_back(make_pair(i, j));
else if(check(i, j - 1))ans.push_back(make_pair(i, j - 1));
else if(check(i - 1, j))ans.push_back(make_pair(i - 1, j));
else if(check(i - 1, j - 1))ans.push_back(make_pair(i - 1, j - 1));
else
{
cout << -1 << endl;
return 0;
}
}
}
sort(ans.begin(), ans.end());
int size = unique(ans.begin(), ans.end()) - ans.begin();
cout << size << endl;
for(int i = 0; i < size; ++i)cout << ans[i].first << " " << ans[i].second << endl;
// cout << endl << (clock() - pp) / CLOCKS_PER_SEC << endl;
return 0;
}
C Gas Pipeline
dp?! 沒怎麼訓練過dp,,暫時扔了,,
D Number Of Permutations
感覺這道題不錯,,
題意就是對于給你的一個二進制對 序列s,,他的排列中任意一維滿足不遞減的排列就是 壞的排列,問你所有的排列中好的共有幾種,,
一開始被tag的組合吓懵了,,以為是什麼推公式的排列組合題,,
其實解法很簡單,,考慮反面就行了,,,總的排列的情況一共有 \(fac[n]\) 種,,然後對于第一維不遞減的排列的個數記為 \(cnt_1\) ,同理第二維的就是 \(cnt_2\) ,,根據容斥的思想,,還有它倆的交集 \(cnt_{12}\) ,,最後他們的答案就是 \(fac[n] - cnt_1 - cnt_2 + cnt_{12}\) ,,,
前兩種的求法就是排序後,,如果沒有重複的元素,那就就是一種情況,,如果有重複的元素,,那麼就是重複元素的階乘的積,,
對于最後這種交集的情況,首先要按第一維排序,如果第一維相等,按第二維排序,,,然後判斷第二維是不是不遞減的,,如果不是不遞減的,,那麼這種情況就是0種,,否者的話,,對于那些相同的二進制對就可以互換位置,,那麼答案就是他們的階乘的積,,
最後統計答案就行了,,記得多加幾個模,,因為前兩種的情況可能很多,,,emmmm,,,wa了好幾發,,,
#include <bits/stdc++.h>
#define aaa cout<<233<<endl;
#define endl '\n'
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
// mt19937 rnd(time(0));
const int inf = 0x3f3f3f3f;//1061109567 > 1e9
const ll linf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-7;
const double pi = 3.14159265358979;
const int maxn = 3e5 + 5;
const int maxm = 1e3 + 5;
// const int mod = 1e9 + 7;
const int mod = 998244353;
pair<int, int> a[maxn];
bool cmpab(pair<int, int> i, pair<int, int> j)
{
if(i.first == j.first)return i.second < j.second;
return i.first < j.first;
}
bool cmpb(pair<int, int> i, pair<int, int> j)
{
return i.second < j.second;
}
ll fac[maxn];
void init()
{
fac[0] = fac[1] = 1;
for(int i = 2; i < maxn; ++i)fac[i] = fac[i - 1] * i % mod;
}
int main()
{
// double pp = clock();
// freopen("233.in", "r", stdin);
// freopen("233.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int n; cin >> n;
for(int i = 1; i <= n; ++i)cin >> a[i].first >> a[i].second;
sort(a + 1, a + 1 + n, cmpab);
ll cnt1, cnt2, cnt12;
cnt1 = cnt2 = cnt12 = 1;
init();
for(int i = 1; i <= n; ++i)
{
int l = i, r = n;
int k = i;
while(l <= r)
{
int mid = l + r >> 1;
if(a[mid].first == a[i].first)
{
l = mid + 1;
k = mid;
}
else
{
r = mid - 1;
}
}
cnt1 = cnt1 * fac[k - i + 1] % mod;
i = k;
}
bool flag = true;
for(int i = 1; i <= n; ++i)if(a[i].second < a[i - 1].second)flag = false;
if(flag)
{
for(int i = 1; i <= n; ++i)
{
int l = i, r = n;
int k = i;
while(l <= r)
{
int mid = l + r >> 1;
if(a[mid].first == a[i].first && a[mid].second == a[i].second)
{
l = mid + 1;
k = mid;
}
else
{
r = mid - 1;
}
}
cnt12 = cnt12 * fac[k - i + 1] % mod;
i = k;
}
}
else
{
cnt12 = 0;
}
sort(a + 1, a + 1 + n, cmpb);
for(int i = 1; i <= n; ++i)
{
int l = i, r = n;
int k = i;
while(l <= r)
{
int mid = l + r >> 1;
if(a[mid].second == a[i].second)
{
l = mid + 1;
k = mid;
}
else
{
r = mid - 1;
}
}
cnt2 = cnt2 * fac[k - i + 1] % mod;
i = k;
}
// cout << fac[n] << " " << cnt1 << " " << cnt2 << " " << cnt12 << endl;
if(n != 1)cout << (fac[n] - cnt1 - cnt2 + cnt12 + mod * 2) % mod << endl;
else cout << 0 << endl;
// cout << endl << (clock() - pp) / CLOCKS_PER_SEC << endl;
return 0;
}
E XOR Guessing
一道簡單的互動題,,,
題意就是你有兩次詢問機會,,每次詢問是100 個數,,然後互動器會選擇一個數和答案 \(x\) 的異或作為輸入給你,,最後你要得出答案那個數,,,
看到異或,第一反應就是位運算相關的,,,往上靠就行了,,隻有兩次機會的話,,而且書的範圍是14位内的正整數,,,是以考慮第一次詢問 \(x\) 的高7位,,後一次詢問低7位,,,然後将得到的值掐掉前面的低7位,,“并” 上後面掐掉高7位的值就行了,,,
忘記将
#define '\n' endl
注釋ile了一發,,,emmmmm
#include <bits/stdc++.h>
#define aaa cout<<233<<endl;
// #define endl '\n'
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
// mt19937 rnd(time(0));
const int inf = 0x3f3f3f3f;//1061109567 > 1e9
const ll linf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-7;
const double pi = 3.14159265358979;
const int maxn = 1e3 + 5;
const int maxm = 1e3 + 5;
const int mod = 1e9 + 7;
int main()
{
// double pp = clock();
// freopen("233.in", "r", stdin);
// freopen("233.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cout << "? ";
for(int i = 1; i <= 100; ++i)cout << i << " ";cout << endl;fflush(stdout);
ll a; cin >> a;
cout << "? ";
for(int i = 1; i <= 100; ++i)cout << (i << 7) << " "; cout << endl;fflush(stdout);
ll b; cin >> b;
// cout << a << b << endl;
a = a & (0b11111110000000);
b = b & (0b00000001111111);
cout << "! " << (a | b) << endl;fflush(stdout);
// cout << endl << (clock() - pp) / CLOCKS_PER_SEC << endl;
return 0;
}
F Remainder Problem
這題也不錯,,
題意就是一個長為500000的數組,,一個操作是對 第x位 a[x] += y;另一種操作是詢問所有 模x餘數為y位置處的數的和,,,
自己想的做法T了,,,因為沒有想到 修改一個數他所會影響的可能詢問該怎麼表示,,,,
這題的解法是: 用一個數組 \(sum[x][y]\) 儲存模為x時餘數時y的答案,,因為當模數很大時,,我們即使時暴力找,,因為這時的數很少,,,是以詢問不怎麼費時間,,,但是數小時,,,尋找的數就很多,,,這樣就會T,,,是以我們隻儲存前750個模數的答案,,,
每次修改一個數 \(a[x] += y\) 後,,,對于所有 \(sum[i][x \% i]\) 都會産生影響,,,這裡的i就是模數,,,\(x \% i\) 相當于是這個模數下的餘數,,當詢問 \((2, i, x \% i)\) 時,,,這個答案就可以直接得到,,,
比如說我修改 a[7] 的值,,那麼對于一個詢問 \((x, y)={(3, 1), (4, 3), (5, 2)......}\) 這些詢問的值一定會改變,,,也就是對 \(sum[3][1], sum[4][7 \% 4], sum[5][7 \% 5]\) 進行了修改,,
思路理清代碼就簡單了,,,
#include <bits/stdc++.h>
#define aaa cout<<233<<endl;
#define endl '\n'
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
// mt19937 rnd(time(0));
const int inf = 0x3f3f3f3f;//1061109567 > 1e9
const ll linf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-7;
const double pi = 3.14159265358979;
const int maxn = 5e5 + 5;
const int maxm = 1e3 + 5;
const int mod = 1e9 + 7;
int a[maxn];
const int k = 750;
int sum[k][k];
int main()
{
// double pp = clock();
// freopen("233.in", "r", stdin);
// freopen("233.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int q; cin >> q;
int o, x, y;
while(q--)
{
cin >> o >> x >> y;
if(o == 1)
{
a[x] += y;
for(int i = 1; i < k; ++i)sum[i][x % i] += y;
}
else
{
if(x >= k)
{
int ans = 0;
for(int i = y; i <= 500000; i += x)ans += a[i];
cout << ans << endl;
}
else
{
cout << sum[x][y] << endl;
}
}
}
// cout << endl << (clock() - pp) / CLOCKS_PER_SEC << endl;
return 0;
}
G Indie Album
貌似是AC自動機的題,,,沒開字元串的專題,,先扔了,,,
(end...)
轉載于:https://www.cnblogs.com/31415926535x/p/11460682.html