--- 題型 ---
放剩下 相關的題目 ψ(._. )>
/*
* zerojudge
* f637. DF-expression
* AC (81ms, 3.4MB)
*/
#include <bits/stdc++.h>
using namespace std;
string s;
int D;
int solve(int &i, int cnt) {
if (i >= s.size()) {
return 0;
}
//
if (s[i] == '1') {
i++;
return D / cnt;
} else if (s[i] == '2') {
i++;
int sum = 0;
for (int j = 0; j < 4; j++) {
sum += solve(i, cnt * 4);
}
return sum;
} else if (s[i] == '0') {
i++;
return 0;
}
return 0;
}
int main() {
cin >> s;
int n;
cin >> n;
D = n * n;
int i = 0;
cout << solve(i, 1) << endl;
return 0;
}/*
* AP325
* P-1-7. 子集合乘積
*/
#include<bits/stdc++.h>
using namespace std;
int n;
int f(int a[],int i,int sum){
if(i>=n){
cout << sum << endl;
return 0;
}
f(a, i + 1, ((sum==0) ? 1 : sum) * a[i]);
f(a, i + 1, sum);
}
int main(){
cin >> n;
int a[n];
int p=10009;
for(int i=0;i<n;i++){
cin >> a[i];
}
f(a,0,0);
}/*
* AP325
* Q-1-8. 子集合的和
*/
#include<bits/stdc++.h>
using namespace std;
int n,P;
vector<int> a;
int max_sum = -1;
void f(int cnt, int sum) {
if (cnt == n) {
if (sum <= P) {
max_sum = max(max_sum, sum);
}
return;
}
f(cnt + 1, sum);
f(cnt + 1, sum + a[cnt]);
}
int main(){
cin >> n >> P;
for(int i=0;i<n;i++){
int x;
cin >> x;
a.push_back(x);
}
f(0,0);
cout << max_sum << endl;
}/*
* AP325
* P-1-9. N-Queen 解的個數
*/
#include<bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n;
int cnt = 0;
int solve(int row,int col,vector<vector<int>> &board){
if(row>=n){
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cout << board[i][j] << " ";
}
cout << "\n";
}
cout << "\n";
cnt+=1;
return 0;
}
for (int col = 0; col < n; col++) { //試橫的
bool isOk = true;
// 檢查|直的
for (int i = 0; i < row; ++i) {
if (board[i][col] == 1) {
isOk=false;
}
}
// 檢查\主對角線
for (int i = row, j = col; i >= 0 && j >= 0; --i, --j) {
if (board[i][j] == 1) {
isOk=false;
}
}
// 檢查/副對角線
for (int i = row, j = col; i >= 0 && j < n; --i, ++j) {
if (board[i][j] == 1) {
isOk=false;
}
}
//
int isPut = false;
if(isOk){ //可以放為1 往下走
isPut = true;
board[row][col] = 1;
solve(row+1,col, board);
board[row][col] = 0;
}
if(col==n-1 && isPut==false){
solve(row+1,0, board);
}
}
return 0;
}
int main(){
cin >> n;
vector<vector<int>>board(n, vector<int>(n, 0));
solve(0,0,board);
cout << "all: " << cnt << endl;
}/*
* AP325
* Q-1-10. 最多得分的皇后
*/
#include<bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n;
int cnt = 0;
int max_sum = 0;
int solve(int row,int col,vector<vector<int>> &board,vector<vector<int>> &score){
if(row>=n){
int sum = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cout << board[i][j] << " ";
if(board[i][j]){
sum+=score[i][j];
}
}
cout << "\n";
}
cout << "\n";
max_sum = (max_sum>sum) ? max_sum : sum;
return 0;
}
for (int col = 0; col < n; col++) { //試橫的
bool isOk = true;
// 檢查|直的
for (int i = 0; i < row; ++i) {
if (board[i][col] == 1) {
isOk=false;
}
}
// 檢查\主對角線
for (int i = row, j = col; i >= 0 && j >= 0; --i, --j) {
if (board[i][j] == 1) {
isOk=false;
}
}
// 檢查/副對角線
for (int i = row, j = col; i >= 0 && j < n; --i, ++j) {
if (board[i][j] == 1) {
isOk=false;
}
}
//
int isPut = false;
if(isOk){ //可以放為1 往下走
isPut = true;
board[row][col] = 1;
solve(row+1,col, board,score);
board[row][col] = 0;
}
if(col==n-1 && isPut==false){
solve(row+1,0, board,score);
}
}
return 0;
}
int main(){
cin >> n;
vector<vector<int>>board(n, vector<int>(n, 0));
vector<vector<int>>score(n, vector<int>(n, 0));
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin >> score[i][j];
}
}
solve(0,0,board,score);
cout << "all: " << cnt << endl;
cout << "max score: " << max_sum << endl;
}/*
* NeetCode
* Products of Array Discluding Self
*/
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
vector<int>v;
int n = nums.size();
int lS[n];
int rS[n];
lS[0]=nums[0];
rS[n-1]=nums[n-1];
for(int i=1;i<n;++i){
lS[i]=lS[i-1]*nums[i];
rS[n-1-i]=rS[n-i]*nums[n-1-i];
}
//
for(int i=0;i<n;i++){
if(i==0){
v.push_back(rS[i+1]);
}else if(i==n-1){
v.push_back(lS[n-1-1]);
}else{
v.push_back(lS[i-1]*rS[i+1]);
}
}
return v;
}
};/*
* CSES
* Restaurant Customers
*/
#include<bits/stdc++.h>
using namespace std;
struct P{
int time;
bool state; // 0 left 1 right
};
bool cmp(P a, P b){
return a.time<b.time;
}
int main(){
int n;
vector<P>v;
cin >> n;
for(int i=0;i<n;++i){
P a,b;
cin >> a.time >> b.time;
a.state = 0;
b.state = 1;
v.push_back(a);
v.push_back(b);
}
sort(v.begin(),v.end(),cmp);
//
int cnt = 0;
int M = -1;
for(int i=0;i<2*n;++i){
if(v[i].state==0){
cnt+=1;
}else if(v[i].state==1){
cnt-=1;
}
//
if(cnt > M){
M = cnt;
}
}
cout << M << endl;
}/*
* CSES
* Static Range Sum Queries
*/
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,q;
cin >> n >> q;
int v[n+1];
int sum = 0;
for(int i=1;i<=n;++i){
int x;
cin >> x;
sum+=x;
v[i]=sum;
}
for(int i=0;i<q;++i){
int a,b;
cin >> a >> b;
cout << v[b]-v[a-1] << endl;
}
}/*
* AP325
* Q-3-13. X 差值範圍內的最大 Y 差值
*/
#include<bits/stdc++.h>
using namespace std;
int main() {
int n, l;
cin >> n >> l;
unordered_map<int, pair<int, int>> ht;
vector<pair<int, int>> v;
int M = -1;
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
if (ht.count(x + l)) {
v.push_back({ht[x + l].second, i});
}
if (ht.count(x - l)) {
v.push_back({ht[x - l].second, i});
}
ht[x] = {x, i};
}
int y[n];
for (int i = 0; i < n; ++i) {
cin >> y[i];
}
for (auto num : v) {
M = max(M, abs(y[num.second] - y[num.first]));
}
cout << M << endl;
return 0;
}#include<bits/stdc++.h>
using namespace std;
int n;
int m = INT_MAX;
void f(int p[],int sum1,int sum2,int i){
if(i==n){
m = min(abs(sum1-sum2),m);
return;
}
//
sum1+=p[i];
f(p,sum1,sum2,i+1);
sum1-=p[i];
//
sum2+=p[i];
f(p,sum1,sum2,i+1);
sum2-=p[i];
}
int main(){
cin >> n;
int p[n];
for(int i=0;i<n;++i){
cin >> p[i];
}
f(p,0,0,0);
cout << m << endl;
}/*
* CSES
* Creating Strings
*/
#include<bits/stdc++.h>
using namespace std;
vector<char>v;
vector<string>v2;
int main(){
string s;
cin >> s;
for(int i=0;i<s.size();++i){
v.push_back(s[i]);
}
sort(v.begin(),v.end());
int cnt = 0;
do {
string x = "";
for (int i = 0; i < v.size(); i++) {
x+=v[i];
}
v2.push_back(x);
cnt+=1;
} while (next_permutation(v.begin(), v.end()));
//
cout << cnt << endl;
for(string x:v2){
cout << x << endl;
}
}/*
* codeforces
* E. Special Elements
*/
#include<bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> arr(n);
set<int>s;
for(int i=0; i<n; ++i) {
cin >> arr[i];
}
for(int l=0;l<n; ++l) {
int sum = arr[l];
for (int r=l+1; r<n; ++r) {
sum += arr[r];
if (sum > n){
break;
}else{
for (int i = 0; i < n; ++i) {
if (arr[i] == sum) {
s.insert(i);
}
}
}
}
}
cout << s.size() << endl;
}
return 0;
}/*
* NCOJ
* 99 . [Tutorial] 趕不完的作業 2
*/
#include<bits/stdc++.h>
using namespace std;
bool cmp(int a,int b){
return a<b;
}
int main(){
int n,l;
cin >> n >> l;
int arr[n];
for(int i=0;i<n;++i){
cin >> arr[i];
}
sort(arr,arr+n,cmp);
int t = 0;
int ans = 0;
for(int i=0;i<n;++i){
if (t+l <= arr[i]) {
t += l;
ans += 1;
}
}
cout << ans << endl;
}/*
* TIOJ
* 1356. 河內之塔-便當塔
*/
#include<bits/stdc++.h>
using namespace std;
int cnt = 0;
void f(int n, int from, int temp, int to) {
if (n == 1) {
cnt += 1;
printf("#%d : move the dish from #%d to #%d\n", cnt, from, temp);
//
cnt += 1;
printf("#%d : move the dish from #%d to #%d\n", cnt, temp, to);
//
return;
}
f(n - 1, from, temp, to);
//
cnt += 1;
printf("#%d : move the dish from #%d to #%d\n", cnt, from, temp);
//
f(n - 1, to, temp, from);
//
cnt += 1;
printf("#%d : move the dish from #%d to #%d\n", cnt, temp, to);
//
f(n - 1, from, temp, to);
}
int main() {
int n;
cin >> n;
f(n, 1, 2, 3);
}
/*
* zerojudge
* i644. 列舉八皇后問題所有解
*/
#include<bits/stdc++.h>
using namespace std;
int ans = 0;
// 檢查是否可以放置皇后
bool isSafe(int table[8][8], int row, int col) {
for (int i = 0; i < row; i++) {
if (table[i][col]) {
return false;
}
}
for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
if (table[i][j]) {
return false;
}
}
for (int i = row, j = col; i >= 0 && j < 8; i--, j++) {
if (table[i][j]) {
return false;
}
}
return true;
}
// 使用回溯法解 N 皇后問題
void queens(int table[8][8], int row,vector<int> &result) {
if (row == 8) {
ans+=1;
printf("%d: %d%d%d%d%d%d%d%d\n",ans,result[0],result[1],result[2],result[3],result[4],result[5],result[6],result[7]);
return;
}
for (int i = 0; i < 8; i++) {
if (isSafe(table, row, i)) { // 檢查是否安全
table[row][i] = 1; // 放置皇后
result[row] = i+1;
queens(table, row + 1,result); // 繼續放置下一行的皇后
table[row][i] = 0; // 回溯
result[row] = 0;
}
}
}
int main() {
int table[8][8] = {0}; // 初始化棋盤
vector<int>result(8);
queens(table,0,result); // 開始從第 0 行放置皇后
return 0;
}
/*
* CSES
* Maximum Subarray Sum
*/
#include<bits/stdc++.h>
using namespace std;
int n;
int a[400000]; // 2*100000
int main(){
cin >> n;
int a[n];
for(int i=0;i<n;++i){
cin >> a[i];
}
//
int now_M = a[0];
int ans_M = a[0];
for(int i=1;i<n;++i){
now_M = max(now_M+a[i],a[i]);
ans_M = max(ans_M,now_M);
}
//
cout << ans_M << endl;
}/*
* zerojudge
* g597. 3. 生產線
*/
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
vector<long long>t(n+1);
vector<long long>diff(n+2,0);
//
for(int i=1;i<=m;++i){
int l,r,w;
cin >> l >> r >> w;
diff[l] += w;
diff[r+1] -= w;
}
for(int i=1;i<=n;++i){
cin >> t[i];
}
//
vector<int>demand(n+1,0);
demand[1] = diff[1];
for(int i=2;i<=n;++i){
demand[i] = demand[i-1] + diff[i];
}
//
demand.erase(demand.begin());
t.erase(t.begin());
sort(t.begin(),t.end());
sort(demand.rbegin(),demand.rend());
//
long long total_time=0;
for(int i=0;i<n;++i){
total_time += (t[i]*demand[i]);
}
cout << total_time << endl;
//
return 0;
}
Last updated
Was this helpful?