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() {
n=read(),m=read();
for (int i=1;i<=n;i++) a[i]=read();
sort(a+1,a+1+n);
while(m--)
{
int x=read();
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;
}
Dichotomous answer
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
\(B \) money
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
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
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
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
The essence of greedy simplification
- De denominator
- Remove public items
- Out of useless items, that is, it can't be better
- 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;
int now[20010],sum[20010],ans[20010],add[20010];
struct Node {
int a;
int b;
long long a_b;
}node[1010];
int read() {
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) {
memset(add,0,sizeof(add));
for(int i=1;i<=ans[0];i++) {
ans[i]=ans[i]*x;
add[i+1]+=ans[i]/10;
ans[i]%=10;
}
for(int i=1;i<=ans[0]+4;i++) {
ans[i]+=add[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) {
memset(add,0,sizeof(add));
int q=0;
for(int i=ans[0];i>=1;i--) {
q*=10;
q+=ans[i];
add[i]=q/x;
if(add[0]==0 && add[i]!=0) {
add[0]=i;
}
q%=x;
}
return 0;
}
bool compare() {
if(sum[0]==add[0]) {
for(int i=add[0];i>=1;i--) {
if(add[i]>sum[i]) return 1;
if(add[i]<sum[i]) return 0;
}
}
if(add[0]>sum[0]) return 1;
if(add[0]<sum[0]) return 0;
}
void cp () {
memset(sum,0,sizeof(sum));
for(int i=add[0];i>=0;i--) {
sum[i]=add[i];
}
return ;
}
bool cmp(Node a,Node b) {
return a.a_b<b.a_b;
}
int main() {
int n=read();
for(int i=0;i<=n;i++) {
node[i].a=read(),node[i].b=read();
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
- The problem must be solved optimally, and the cost change from the current state to another state must be 1
DFS
- , 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;
}