Algorithm practice log

1. Maximum suborder sum (Monotone Queue)

Site link: Acwing 135 Title description

Input a sequence of integers of length N, find a continuous subsequence of length not more than m, so that the sum of all numbers in the subsequence is maximum

Note: The length of the subsequence is at least 1.

Input format

Enter two integers n,m on the first line. In the second line, enter n numbers representing a sequence of integers of length N. Numbers in the same line are separated by Spaces.

The output format

Output an integer representing the largest sum of suborders of the sequence.

Data range

1 n or less, 300000 m or less

Example Input:

6 4

1 -3 5 1 -2 3

Example output:

7

#include <iostream> #include<vector> #include<list> using namespace std; typedef long long LL; vector<LL> sum; list <int> queIndex; LL maxNum = 0; int main() { int n,m; int num; cin>>n>>m; sum.push_back(0); for(int i=1; i<n+1; i++) { cin>>num; sum.push_back(num+sum[i-1]); } maxNum = sum[1]; queIndex.push_back(0); queIndex.push_back(1); for(int i =2; i<sum.size(); i++) { while(! queIndex.empty()&&i-queIndex.front()>m) queIndex.pop_front(); if((sum[i]-sum[queIndex.front()])>maxNum) maxNum = sum[i]-sum[queIndex.front()]; while(! queIndex.empty()&&sum[i]<sum[queIndex.back()]) queIndex.pop_back(); queIndex.push_back(i); } cout<<maxNum; return 0; }Copy the code

Ii. Counterfeit currency problem (Enumeration method)

OpenJudge 2692: Counterfeit currency problem

Total time limit: 1000ms memory limit: 65536kB

describe

Sally has 12 silver coins. There are 11 real coins and one fake one. Fake money looks the same as real money, but the weight is different. But Sally doesn’t know if the fake money is lighter or heavier than the real thing. So he borrowed a pair of scales from a friend. The friend wanted Sally to say that in three tries she could spot the fake money and determine whether it was light or heavy. For example, if Sai uses a scale to weigh two coins and finds the balance, both coins are real. If Sai compares a real coin with another silver coin and finds that it is lighter or heavier than the real coin, it is a counterfeit. After carefully arranging each weigh-in, Sallie guaranteed to identify the counterfeit after weighing it three times.

The input

The first line has a number n, indicating that there are n sets of test cases. For each set of test cases: There are three lines of input, each representing the result of a single weighing. Sallie had previously labeled the silver coins A-L. The result of each weighing is represented by three strings separated by Spaces: coins placed on the left side of the balance coins placed on the right side of the balance. The state of equilibrium is represented by up, down, or even, which are high on the right, low on the right, and balanced respectively. The balance always has the same number of coins left and right.

The output

Output which label of silver coin is counterfeit and indicate whether it is heavier or lighter than the real coin.

The sample input

1

ABCD EFGH even

ABCI EFJK up

ABIJ EFGH even

Sample output

K is the counterfeit coin and it is light.

source

East Central North America 1998 Introduction to Computing 05

#include <iostream> #include<stdio.h> using namespace std; int status[12]; char leftStr[3][7],rightStr[3][7],result[3][7]; bool isFailCoin() { int leftStrW,rightStrW; for(int i=0; i<3; i++) { leftStrW = rightStrW =0; for(int j =0; j<6&&leftStr[i][j]! = 0; j++) { leftStrW+=status[leftStr[i][j]-'A']; rightStrW+=status[rightStr[i][j]-'A']; } if(leftStrW==rightStrW&&result[i][0]! ='e') return false; if(leftStrW<rightStrW&&result[i][0]! ='d') return false; if(leftStrW>rightStrW&&result[i][0]! ='u') return false; } return true; } int main() { int n; cin>>n; while(n-->0) { int i; for(i =0; i<3; i++) { scanf("%s %s %s",leftStr[i],rightStr[i],result[i]); The fill (status, the status + 12, 0); } for(i=0; i<12; i++) { status[i]=1; if(isFailCoin()) break; status[i]=-1; if(isFailCoin()) break; status[i]=0; } cout<<char(i+'A')<<" is the counterfeit coin and it is "<<string(status[i]>0?" heavy.":"light.")<<endl; }; return 0; }Copy the code

This article uses the article synchronization assistant to synchronize