Date Statistics
The first four digits are fixed. Generate the last four digits using nested loops, record valid dates, then verify if these dates can be formed.
Verification method: Since it's a subsequence problem, we can skip elements but maintain relative order. For the given 100 numbers, match each digit sequentially with the 8-digit date. If all 8 digits match successfully, the date is valid.
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
int months[13] = {-1,31,29,31,30,31,30,31,31,30,31,30,31};
void process() {
set<int> validDates;
int sequence[100] = {5,6,8,6,9,1,6,1,2,4,9,1,9,8,2,3,6,4,7,7,5,9,5,0,3,8,7,5,8,1,5,8,6,1,8,3,0,3,7,9,2,
7,0,5,8,8,5,7,0,9,9,1,9,4,4,6,8,6,3,3,8,5,1,6,3,4,6,7,0,7,8,2,7,6,8,9,5,6,5,6,1,4,0,1,
0,0,9,4,8,0,9,1,2,8,5,0,2,5,3,3};
for(int i = 0; i <= 9; i++) {
for(int j = 0; j <= 9; j++) {
for(int k = 0; k <= 9; k++) {
for(int m = 0; m <= 9; m++) {
int tempDate = 2023;
tempDate = tempDate * 10 + i;
tempDate = tempDate * 10 + j;
tempDate = tempDate * 10 + k;
tempDate = tempDate * 10 + m;
string dateStr = to_string(tempDate);
int monthVal = (dateStr[4] - '0') * 10 + dateStr[5] - '0';
int dayVal = (dateStr[6] - '0') * 10 + dateStr[7] - '0';
if(monthVal >= 1 && monthVal <= 12 && dayVal >= 1 && dayVal <= months[monthVal])
validDates.insert(tempDate);
}
}
}
}
int result = 0;
for(auto date : validDates) {
string target = to_string(date);
int matchedCount = 0;
for(int idx = 0; idx < 100; idx++) {
if(sequence[idx] == target[matchedCount] - '0')
matchedCount++;
}
if(matchedCount == (int)target.size())
result++;
}
cout << result << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int testCases = 1;
while(testCases--) {
process();
}
return 0;
}
Binary String Entropy
Simple formula application. Enumerate counts of 0s and 1s to verify if they satisfy the given equation.
#include<bits/stdc++.h>
#define endl '\n'
#define epsilon 1e-4
#define int long long
using namespace std;
void process() {
for(int zeros = 0; zeros <= 23333333; zeros++) {
int ones = 23333333 - zeros;
if(zeros > ones) break;
double probZero = (double)zeros / 23333333;
double probOne = (double)ones / 23333333;
double entropyZero = (-1) * zeros * probZero * log2(probZero);
double entropyOne = (-1) * ones * probOne * log2(probOne);
double totalEntropy = entropyZero + entropyOne;
if(abs(totalEntropy - 11625907.5798) < epsilon) {
cout << zeros << endl;
return;
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int testCases = 1;
while(testCases--) {
process();
}
return 0;
}
Metal Smelting
Method one: Identify patterns. For example, in the sample:
3
75 3
53 2
59 2
75/3=25
75/4=18
75/25=3
75/24=3
75/23=3
...
75/19=3
75/18=4
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int MAX_N = 1e4 + 10;
int values[MAX_N], targets[MAX_N];
int countN;
void process() {
cin >> countN;
for(int i = 1; i <= countN; i++)
cin >> values[i] >> targets[i];
int maxVal = 2e9, minVal = 0;
for(int i = 1; i <= countN; i++) {
int upper = values[i] / targets[i];
int lower = values[i] / (targets[i] + 1) + 1;
maxVal = min(maxVal, upper);
minVal = max(minVal, lower);
}
cout << minVal << ' ' << maxVal << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int testCases = 1;
while(testCases--) {
process();
}
return 0;
}
Method two: Binary search
Binary search in [1,1e9] for an answer.
For minimum conversion rate, for each answer, check if all records satisfy output ≤ targets[i]. Return true if satisfied, find the smallest value that returns true.
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int MAX_N = 1e4 + 10;
int values[MAX_N], targets[MAX_N];
int countN;
bool validateMin(int rate) {
for(int i = 1; i <= countN; i++) {
if(values[i] / rate > targets[i])
return false;
}
return true;
}
bool validateMax(int rate) {
for(int i = 1; i <= countN; i++) {
if(values[i] / rate < targets[i])
return false;
}
return true;
}
void process() {
cin >> countN;
for(int i = 1; i <= countN; i++)
cin >> values[i] >> targets[i];
int left = 1, right = 1e9;
while(left < right) {
int mid = (left + right) >> 1;
if(validateMin(mid))
right = mid;
else
left = mid + 1;
}
int minValue = left;
left = 1, right = 1e9;
while(left < right) {
int mid = (left + right + 1) >> 1;
if(validateMax(mid))
left = mid;
else
right = mid - 1;
}
int maxValue = left;
cout << minValue << ' ' << maxValue << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int testCases = 1;
while(testCases--) {
process();
}
return 0;
}
Airplane Landing
Small data size, directly enumerate all cases and check if at least one case allows successful landing.
Use permutations.
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int MAX_SIZE = 15;
int arrival[MAX_SIZE], duration[MAX_SIZE], window[MAX_SIZE];
int order[MAX_SIZE];
int numPlanes;
void process() {
cin >> numPlanes;
for(int i = 1; i <= numPlanes; i++)
cin >> arrival[i] >> duration[i] >> window[i], order[i] = i;
do {
bool success = true;
int prevEnd = 0;
for(int i = 1; i <= numPlanes; i++) {
if(arrival[order[i]] + duration[order[i]] < prevEnd) {
success = false;
break;
}
int start = max(prevEnd, arrival[order[i]]);
prevEnd = start + window[order[i]];
}
if(success) {
cout << "YES" << endl;
return;
}
} while(next_permutation(order + 1, order + 1 + numPlanes));
cout << "NO" << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int testCases = 1;
cin >> testCases;
while(testCases--) {
process();
}
return 0;
}
Chain Number Sequence
Ask for minimum deletions, which means maximum retention.
Find longest chain subsequence length, then subtract from total length.
For each number, when used as chain end, its predecessor must have tail equal to current head. So dp[tail] = max(dp[tail], dp[head] + 1).
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int MAX_N = 1e5 + 10;
int dp[MAX_N];
int sequenceLength;
void process() {
cin >> sequenceLength;
int result = 0;
for(int i = 1; i <= sequenceLength; i++) {
string numStr;
cin >> numStr;
int len = numStr.size() - 1;
int headDigit = numStr[0] - '0';
int tailDigit = numStr[len - 1] - '0';
dp[tailDigit] = max(dp[tailDigit], dp[headDigit] + 1);
result = max(result, dp[tailDigit]);
}
cout << sequenceLength - result << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int testCases = 1;
while(testCases--) {
process();
}
return 0;
}
Island Count
Islands touching external sea are not sub-islands.
First mark outer ring as external sea, start search from (0,0), mark all external seas (8 directions) as 2.
Then for internal seas, still marked as 0, mark them as land.
Finally count connected land blocks.
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
typedef pair<int,int> Point;
const int MAX_GRID = 55;
char grid[MAX_GRID][MAX_GRID];
int rows, cols;
int dir8X[8] = {0,0,1,-1,1,1,-1,-1}, dir8Y[8] = {1,-1,0,0,-1,1,-1,1};
int dir4X[4] = {0,0,1,-1}, dir4Y[4] = {1,-1,0,0};
void expandSea(int x, int y) {
grid[x][y] = '2';
for(int i = 0; i < 8; i++) {
int nextX = x + dir8X[i], nextY = y + dir8Y[i];
if(nextX < 0 || nextX > rows + 1 || nextY < 0 || nextY > cols + 1 || grid[nextX][nextY] != '0')
continue;
expandSea(nextX, nextY);
}
}
void exploreLand(int x, int y) {
grid[x][y] = '3';
for(int i = 0; i < 4; i++) {
int nextX = x + dir4X[i], nextY = y + dir4Y[i];
if(nextX < 0 || nextX > rows + 1 || nextY < 0 || nextY > cols + 1 || grid[nextX][nextY] != '1')
continue;
exploreLand(nextX, nextY);
}
}
void process() {
cin >> rows >> cols;
for(int i = 1; i <= rows; i++) {
for(int j = 1; j <= cols; j++) {
cin >> grid[i][j];
}
}
for(int i = 0; i <= rows + 1; i++) {
for(int j = 0; j <= cols + 1; j++) {
if(grid[i][j] == '1' || grid[i][j] == '0') continue;
grid[i][j] = '0';
}
}
expandSea(0, 0);
for(int i = 0; i < rows; i++) {
for(int j = 0; j < cols; j++) {
if(grid[i][j] == '0')
grid[i][j] = '1';
}
}
int islandCount = 0;
for(int i = 1; i <= rows; i++) {
for(int j = 1; j <= cols; j++) {
if(grid[i][j] == '1') {
exploreLand(i, j);
islandCount++;
}
}
}
cout << islandCount << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int testCases = 1;
cin >> testCases;
while(testCases--) {
process();
}
return 0;
}
Substring Abbreviation
Store positions where character equals c1, then when encountering c2, binary search for the largest position satisfying length ≥ k with c2 as end and c1 as start. All preceding c1 positions contribute to answer.
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
int minLength;
string text;
char startChar, endChar;
void process() {
cin >> minLength;
cin >> text;
cin >> startChar >> endChar;
map<char, int> counter;
vector<int> startPos;
int result = 0;
for(int i = 0; i < (int)text.size(); i++) {
if(text[i] == startChar)
startPos.push_back(i);
else if(text[i] == endChar) {
if(!startPos.size())
continue;
int left = 0, right = startPos.size() - 1;
while(left < right) {
int mid = (left + right + 1) >> 1;
if(i - startPos[mid] + 1 >= minLength)
left = mid;
else
right = mid - 1;
}
if(i - startPos[left] + 1 >= minLength)
result += left + 1;
}
}
cout << result << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int testCases = 1;
while(testCases--) {
process();
}
return 0;
}
Integer Deletion
Linear storage deletion has O(n) complexity, linked storage is more suitable.
Use doubly linked list, implemented with arrays.
Use priority queue (min heap) to easily extract minimum value element.
When deleting an element, add its value to both adjacent elements. Since we can't modify elements arbitrarily in priority queue, use a technique: record updated value at index x, don't immediately update priority queue, similar to lazy propagation in segment trees. Update when needed. When front value is current, perform deletion.
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
typedef pair<int,int> Element;
const int MAX_SIZE = 5e5 + 10;
int values[MAX_SIZE];
int leftPtr[MAX_SIZE], rightPtr[MAX_SIZE];
int arraySize, deleteCount;
void removeElement(int pos) {
leftPtr[rightPtr[pos]] = leftPtr[pos];
rightPtr[leftPtr[pos]] = rightPtr[pos];
values[leftPtr[pos]] += values[pos];
values[rightPtr[pos]] += values[pos];
}
void process() {
cin >> arraySize >> deleteCount;
for(int i = 1; i <= arraySize; i++)
cin >> values[i];
for(int i = 1; i <= arraySize; i++)
leftPtr[i] = i - 1;
rightPtr[0] = 1;
for(int i = arraySize; i >= 1; i--)
rightPtr[i] = i + 1;
priority_queue<Element, vector<Element>, greater<Element>> pq;
for(int i = 1; i <= arraySize; i++)
pq.push({values[i], i});
while(deleteCount--) {
auto top = pq.top();
pq.pop();
if(top.first != values[top.second]) {
pq.push({values[top.second], top.second});
deleteCount++;
}
else
removeElement(top.second);
}
for(int i = rightPtr[0]; i <= arraySize; i = rightPtr[i])
cout << values[i] << ' ';
cout << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int testCases = 1;
while(testCases--) {
process();
}
return 0;
}