题目链接：
A.http://codeforces.com/problemset/problem/1143/A
B.http://codeforces.com/problemset/problem/1143/B
C.http://codeforces.com/problemset/problem/1143/C
D.http://codeforces.com/problemset/problem/1143/D
E.http://codeforces.com/problemset/problem/1143/E
F.http://codeforces.com/problemset/problem/1143/F
水题没什么好说的的
题意：给出一个n，要求求出小于n中的所有数的各位乘积的最大的是多少
思路：存下n的每一位，贪心地考虑每一个位置，将这个位置减1，这个位置之前的位保证最大，之后的位置保证全为9，注意特判最大位。
代码：
#include<bits/stdc++.h> using namespace std; const int maxn = 25; int num[maxn]; int main() { int n,cnt = 0; scanf("%d",&n); while(n) { num[cnt++] = n; n /= 10; } int sum = 1,ans = -1; for(int i = cnt - 1;i>=0;i--) sum *= num[i]; ans = sum; for(int i = cnt - 1;i >= 0;i--) { sum = 1; for(int j = cnt - 1;j >= 0;j--) { if(j>i) { sum *= num[j]; } else if(i == j) { if(j == cnt - 1 && num[j] - 1 == 0) { sum*=1; } else sum *= (num[j]-1); } else sum*=9; } ans = max(sum,ans); } printf("%d",ans); return 0; }题意：给出一棵树，每个节点有两种状态，1时代表这个节点可能被删除，0表示这个节点不会会删除，当一个节点的所有儿子节点均为1状态时该节点可以删除，删除后他的儿子节点继承其父亲节点
思路：由于删除节点的所有儿子节点都是1，因此不会有影响，扫一遍即可。
代码：
#include<bits/stdc++.h> using namespace std; const int maxn = 1e5+5; int n; int par[maxn],c[maxn],vis[maxn]; vector<int> G[maxn]; void del(int s) { int x = par[s]; for(int i = 0;i < G[s].size();i++) { par[G[s][i]] = x; } } void solve() { int flag = 1; for(int i = 1;i <= n;i++) { if(c[i]) { if(!vis[i]) { del(i); printf("%d ",i); flag = 0; } } } if(flag) printf("-1"); } int main() { scanf("%d",&n); for(int i = 1;i <= n;i++) { scanf("%d%d",&par[i],&c[i]); if(!c[i]) vis[i] = 1; else { G[par[i]].push_back(i); } } for(int i = 1;i <= n;i++) if(c[par[i]] && !c[i]) vis[par[i]] = 1; solve(); return 0; }
题意：给出n,k,a,b；表示共有nk个城市，这些城市等距围成一个圆，共有n家餐厅，以1，k+1,2k+1.....均匀地分布在这个圆上，a表示当在起始点s的时候，距离餐厅最近的距离，b表示第一次移动l时距离餐厅最近的距离，已知我们以l的步长移动。
思路：等价于同余方程 $ l \equiv \pm a\pm b modk $ 我们可以解出 \(l = kx+l[i]\) 其中x为任意整数,l[i]代表ab的正负情况，总的移动步数 = nk/gcd(nk,l[i]+x*k) 我们从0-n-1枚举x就好，这样我们就求出了最大最小
代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll gcd(ll a,ll b) { return b ? gcd(b,a%b) : a; } ll l[4]; int main() { ll n,k,a,b,now; cin>>n>>k>>a>>b; ll maxans = -1,minans = 1e18; l[0] = (2*k+a+b)%k; l[1] = (2*k+a-b)%k; l[2] = (2*k-a+b)%k; l[3] = (2*k-a-b)%k; for(int i = 0;i < 4;i++) { for(int j = 0;j < n;j++) { now = n*k/gcd(n*k,l[i]+j*k); maxans = max(maxans,now); minans = min(minans,now); } } cout<<minans<<" "<<maxans; return 0; }
题意：给你两个排列a,p，p为1,2,3...n的一个排列,a是长度为m的一个任意排列，现在有q个查询，对于每个[l,r]的查询，表示在排列a 中的[l,r]这个连续序列是否存在子序列是p序列的一个连续段或者能够通过右移得到(也可以把p序列看成一个圆来匹配)
思路：对于A中的每一个Ai，求出 (Ai在P中的前一个数字)在A中的小于i的最大位置b[i]。比如P是(3,2,1),A是(3,1,2,3)，那对于A中的2来说，求出来的b就是1，对于A中第二个3来说，求出来的b就是2,得到的b为(0,0,1,2)。可以通过记录每一个数字最后出现的位置来求每一个Ai的b[i]。 那对于一个A[i],我们算b[b[b[b[…b[i]]…],套n-1次就可以得到[L,i]这个区间存在以A[i]为结尾的循环右移排列需要的最大的L。直接套的话每一个数字都要算N-1次，是O(n²)的算法，所以我们用倍增的思想，f[i][j]代表第i个数字要得到以它为结尾的长度为2^j的排列所需要的最大的区间左端点L，那么显然f[i][0] = b[i],转移方程为f[i][j+1] = f[ f[i][j] ] [ j ], 然后用g[i]表示最大的L使得[L，i]这个区间存在P的循环右移，然后利用f[i][j]算一下第i个要到前n-1需要的最大的L，转移方程是g[i] = max(g[i-1],L)。
代码：
#include<bits/stdc++.h> using namespace std; const int maxn = 2e5 + 50; int pre[maxn]; int n,m,q; int p[maxn],a[maxn],pos[maxn]; int f[maxn][21]; int g[maxn]; int solve(int x,int num){//利用f[i][j]计算x到前num个数需要的最大左端点 for(int i = 20;i >= 0;--i){ if((1<<i)&num) x = f[x][i]; } return x; } int main(){ scanf("%d%d%d",&n,&m,&q); for(int i = 1;i <= n;++i) scanf("%d",&p[i]),pre[p[i]] = p[i-1]; pre[p[1]] = p[n]; for(int i = 1;i <= m;++i){ scanf("%d",&a[i]); pos[a[i]] = i;//记录a[i]这个数字最后一次出现的位置 f[i][0] = pos[pre[a[i]]] ;//a[i]的第一个前驱的位置 for(int j = 0;j < 20;++j) { f[i][j+1] = f[f[i][j]][j]; //a[i]的第2^(j+1)个前驱是a[i]的第2^j个前驱的第2^j个前驱 } g[i] = max(g[i-1],solve(i,n-1)); } while(q--){ int l,r;scanf("%d%d",&l,&r); if(l<=g[r]) printf("1"); else printf("0"); } return 0; }计算几何这种东西就丢给队友了（雾
转载于:https://www.cnblogs.com/pot-a-to/p/11144143.html
