# 2/17qbxt notes (quite complete)

## Caching mechanism

In the computer, there is something faster than reading in the memory. It is called cache. Its definition is that when reading an array from the memory, the computer will predict whether the remaining continuous arrays will be used, so it will be stored in the cache. In this way, it can be read in order directly without query, which is faster.

Then, for our two-dimensional array \ (f[i][j] \), it is a linear long chain composed of \ (I \) line segments with a length of \ (1\times j \), so the continuous numbers are \ (f[1][1],f[1][2] \), not \ (f[1][1],f[2][1] \),

Then, it is extended to our \ (for \) loop. If we loop in the order of outer layer \ (i \) and inner layer \ (j \), the resulting array is called in the order of computer storage, so it can be read directly from the cache. However, when we turn around, the computer cannot predict our order, that is, the array in the cache is useless (current), so we can only call memory, and the time gap is about \ (10 \)

Therefore, the enumeration order of the loop is related to the time complexity Especially for matrix multiplication and division, the extreme value caused by different transportation sequences can reach \ (4 \) times, which is the reason why the latter points are stuck, especially the loss.

## Dichotomy

To solve the problem, a \ (m \) asked that the sequence of numbers has been arranged in order to find out how many are less than \ (x \)

### thinking

If you know the largest \ (a_i < = x \), you can say that the answer is \ (I \)

int n,m,a[B];

int main() {
sort(a+1,a+1+n);
while(m--)
{
int l=1, r=n, ans=0;
while(l<=r)
{
int mid=(l+r)>>1;
if(a[mid]<=x) l=mid+1, ans=mid;
else r=mid-1;
}
printf("%d\n",ans);
}
return 0;
}



Given \ (N \) rope, you are required to divide \ (K \) rope from it, so that the length of each rope is the same and must be an integer. Ask how long this \ (K \) rope can be.

### thinking

This question should be said well. It wasted me an afternoon and gave me a new understanding of double and int

It's easy to do this. The binary length depends on whether the number of segments in the line is greater than \ (K \), and the binary answer is good

But this question needs to use precision, because the number obtained in the process of bisection is always decimal, but what we define is shaping, so it will be infinite loop

Then, in the final cast, I found three different output methods and got three different scores. The process was painful

cout<<a;


This is a direct double precision output, no change

printf("%.f",a)


This is amazing. It can automatically round. It's amazing. I know that the answer is partially correct

int s=(int)a;
cout<<s;


By forcing type conversion, you can get the integer part completely, which is also the final correct answer,

double s[B],sum;
const double esp=1e-8;
int n,k;

main() {
//  freopen(".in", "r", stdin);
//  freopen(".out", "w", stdout);
cin>>n>>k;
double mx=0;
for (int i=1;i<=n;i++)
{
cin>>s[i];
mx=max(mx,s[i]);
}
double l=0,r=mx;
while(l+esp<r)
{
double mid=(l+r)/2;
int num=0;
for (int i=1;i<=n;i++)  num+=s[i]/mid;
if(num>=k) l=mid;
else r=mid;
}
int s=(int)l;
cout<<s;
return 0;
}


## greedy

### King game

How to rank ministers???

Absolutely right-handed. It doesn't seem right, md

Suppose a function of \ (cmp \) is found when \ (n==2 \), and then it can be sorted directly. This is greed. Informatics is a license that does not need to be proved. There is no need to prove. This can be done for the greed problem of \ (\% 90 \), \ (nb \)

### thinking

We might as well set \ (n=2 \), the people who benefit the most from gold coins are the least

The first person \ (a \) is \ (a.r,a.l \), and the second person \ (B \) is \ (b.r,b.l \)

Let the emperor's left and right hands be \ (z[0].l, z[0].r \)

When \ (A \) is in front of \ (B \)

$$A$$ money

$\frac{z[0].l}{a.r}$

$$B$$ money

$\frac{z[0].l\times a.l}{b.r}$

The answer \ (v1 \) is \ (max\{\frac{z[0].l}{a.r},\frac{z[0].l\times a.l}{b.r} \} \)

When \ (B \) precedes \ (A \)

Similarly, the answer \ (v2 \) is \ (max\{\frac{z[0].l}{b.r},\frac{z[0].l\times b.l}{a.r} \} \)

The final answer is \ (max\{v1,v2 \} \)

Well, when \ (n!=2 \), if these two people need us to discuss now, we don't need the number from the king to the left hand of the person in front of us. Let's set this number as \ (x \), then the formula becomes

$v1=max\{\frac{x}{a.r},\frac{x\times a.l}{b.r}\}\\ v2=max\{\frac{x}{b.r},\frac{x\times b.l}{a.r}\}\\$

The answer is \ (ans=max\{v1,v2 \} \)

When we remove the denominator, that is, \ (v1,v2 \) is multiplied by \ (a.r\times b.r \)

Simplified

$v1=max\{b.r\times x,x\times a.l\times a.r\}\\ v2=max\{a.r\times x,x\times b.l\times b.r\}\\$

We find that \ (x \) can be eliminated, that is, the size of the answer here is not affected by \ (x \), so our formula can become

$v1=max\{b.r,a.l\times a.r\}\\ v2=max\{a.r, b.l\times b.r\}\\$

With the formula, we can use bubble sorting, and the time complexity is \ (O(n^2) \)

//Bubble sorting
#include <iostream>

using namespace std;

struct node{
int l,r;
};
node z[100010];

int cmo(node a, node b)//Is a in front of b
{
int v1 = max(z[0].l/a.r, z[0].l*a.l / b.r);
int v2 = max(z[0].l/b.r, z[0].l*b.l / a.r);

if(v1<v2) return 1;
else return 0;
}
int main()
{
for (int i=1;i<=n;i++)
for (int j=1;j<n;j++)
{
if(cmp(z[j+1],z[j])) swap(z[j+1], z[j]);
}
}// O(n^2)


In fact, it becomes comparing the size of these four numbers, so we can be greedy

Can greedy formula be optimized?

It is not difficult to find \ (b.R < b.l \ times b.R \) and \ (A.R < A.l \ times A.R \)

Well, it's meaningful to compare these two. They are essentially larger than the one on the right, so it's good to eliminate them, so the formula is simplified

$ans=max\{b.r\times b.l, a.r\times a.l\}$

The essence of greedy simplification

1. De denominator
2. Remove public items
3. Out of useless items, that is, it can't be better
4. Simplified!
struct node{
int l, r;
};

node z[B];
int ans=1, n;

int cmp(node a, node b)
{
return a.l*a.r<b.l*b.r;
}

int main() {
scanf("%d",&n);
scanf("%d%d",&z[0].l,&z[0].r);
for (int i=1;i<=n;i++)
scanf("%d%d",&z[i].l,&z[i].r);

sort(z+1,z+1+n,cmp);
for (int i=0;i<n;i++) ans*=z[i].l;
printf("%d",ans/z[n].r);
return 0;
}


### High precision practice

#include <bits/stdc++.h>
using namespace std;
struct Node {
int a;
int b;
long long a_b;
}node[1010];
int ans=0,flag=1;
char ch=getchar();
while( (ch>'9' || ch<'0') && ch!='-' ) ch=getchar();
if(ch=='-') flag=-1,ch=getchar();
while(ch>='0' && ch<='9') ans=ans*10+ch-'0',ch=getchar();
return ans*flag;
}
void times(int x) {
for(int i=1;i<=ans[0];i++) {
ans[i]=ans[i]*x;
ans[i]%=10;
}
for(int i=1;i<=ans[0]+4;i++) {
if(ans[i]>=10) {
ans[i+1]+=ans[i]/10;
ans[i]%=10;
}
if(ans[i]!=0) {
ans[0]=max(ans[0],i);
}
}
return ;
}
int divition(int x) {
int q=0;
for(int i=ans[0];i>=1;i--) {
q*=10;
q+=ans[i];
}
q%=x;
}
return 0;
}
bool compare() {
}
}
}
void cp () {
memset(sum,0,sizeof(sum));
}
return ;
}
bool cmp(Node a,Node b) {
return a.a_b<b.a_b;
}
int main() {
for(int i=0;i<=n;i++) {
node[i].a_b=node[i].a*node[i].b;
}
sort(node+1,node+n+1,cmp);
ans[0]=1,ans[1]=1;
for(int i=1;i<=n;i++) {
times(node[i-1].a);
divition(node[i].b);
if(compare()) {
cp();
}
}
for(int i=sum[0];i>=1;i--)
printf("%d",sum[i]);
return 0;
}


## Input output optimization

### Get out

char s[10000000];
int l=0;

void print(int x)
{
int y=0,z=0;//Reverse writing
while (x!=0)
{
y=y*10+x%10;
z++;
x/=10;
}
for (int a=1;a<=z;a++)
{
s[l++]=y%10+'0';
y/=10;
}
s[l++]='\n';
}


## Calculation method of space

• $$char$$ 1 byte
• $$int$$ 4 bytes
• $$long\ long$$ 8 bytes
• $$1M=1024K$$
• $$10^7=10M$$

## search

• BFS
• DFS

Question type: choose the number of \ (k \) for the number of \ (N \)

Summation minimum optimal solution problem

Finding the number of schemes -- solving the number quantity problem

A feasible solution problem is given

## How to determine which search method to use

BFS

1. The problem must be solved optimally, and the cost change from the current state to another state must be 1

DFS

1. , the rest are DFS

## Search optimization

### Feasible pruning

Throw away the obviously impossible solution directly

### Optimal pruning

Can't be the most solved pruning

void dfs(int p, int nowsum, int nowuse)//Considering p, and is nowsum, the number of nowuse s is selected
{
if (nowuse>k) return;//Feasible pruning
if (nowuse + n-p+1 < k) return;//Feasible pruning
if (nowsum>=ans) return;//Optimal pruning
if(p>n)
{
ans=min(nowsum,k);
return;
}
dfs(p+1,nowsum,nowuse);
dfs(p+1,nowsum+a[p];nowsue+1);
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
dfs(1,0,0);
printf("%d",ans);
return 0;
}


### Search order optimization

If the order is followed by search, the search order will be affected, that is, search the feasibility optimal solution first

You can choose questions that can make the answer better or faster to the answer

Target center number

void dfs(int p, int nowsum, int nowuse)//Considering p, and is nowsum, the number of nowuse s is selected
{
if (nowuse>k) return;//Feasible pruning
if (nowuse + n-p+1 < k) return;//Feasible pruning
if (nowsum>=ans) return;//Optimal pruning
if(p>n)
{
ans=min(nowsum,k);
return;
}
dfs(p+1,nowsum+a[p];nowsue+1);
dfs(p+1,nowsum,nowuse);

}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+1+n);
dfs(1,0,0);
printf("%d",ans);
return 0;
}


Posted by Skepsis on Mon, 18 Apr 2022 12:42:55 +0930