A - Jzzhu and Children
找到最大的ceil(a/m)即可
#include <iostream>
#include <cmath>
using namespace std; int main(){
int n,m;
cin >> n >> m;
double a, maxv = ;
int maxIdx = ;
for(int i = ; i < n; ++ i){
cin >> a;
if(maxv <= ceil(a/m)){
maxv = ceil(a/m);
maxIdx = i+;
}
}
cout<<maxIdx<<endl; }
B - Jzzhu and Sequences
f= f-f
f=x, f=y, f3=y-x, f4 = y-x-y = -x, f5 = -x-(y-x) = -y , f6 =-y-(-x) = x-y
f7 = x-y-(-y)=x, f8 = x-(x-y) = y...........
注意该序列的循环节是6
只要算出前六个数即可。
#include <iostream>
#include <vector>
#define ll long long
#define MOD 1000000007
using namespace std; int main(){
ll x,y,n;
cin >> x >> y >> n;
vector<ll> f(,);
f[] =x;f[]=y;
for(int i = ; i < ; ++ i) f[i] = f[i-]-f[i-];
cout<<(f[(n-)%]%MOD+MOD)%MOD<<endl;
}
利用循环节
本题也可以采用矩阵快速幂运算
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <utility>
#define ll long long
#define MOD 1000000007
using namespace std; struct matrix
{
ll m[][];
}ans, base; matrix multi(matrix a, matrix b)
{
matrix tmp;
for(int i = ; i < ; ++i)
{
for(int j = ; j < ; ++j)
{
tmp.m[i][j] = ;
for(int k = ; k < ; ++k)
tmp.m[i][j] = (tmp.m[i][j] + a.m[i][k] * b.m[k][j]);
}
}
return tmp;
}
ll fast_mod(ll n,ll x,ll y)
{
base.m[][] = ;
base.m[][] = -;
base.m[][] = ;
base.m[][] = ;
ans.m[][] = ans.m[][] = ;
ans.m[][] = ans.m[][] = ;
while(n)
{
if(n & )
{
ans = multi(ans, base);
}
base = multi(base, base);
n >>= ;
} return ans.m[][]*y+ans.m[][]*x;
} int main(){
ll x,y,n;
cin >> x >> y >> n;
ll res = ;
if(n == ) res = x;
else if(n == ) res = y;
else res = fast_mod(n-,x,y);
if(res < ) res = res%MOD;
cout<<(res+MOD)%MOD<<endl;
}
矩阵快速幂运算
注意结果输出时对负数要 (res%mod+mod)%mod，因为res可能大于mod， 不然结果可能被cha掉
C - Jzzhu and Chocolate
题目的意思：
给nxm的巧克力，切k刀后，求最小块巧克力的最大面积
解题思路：
可以假设n<m，如果n>m，则交换n和m。
现在将行分成x行，列分成y列，相当于行切x-1次，列切y-1次，x-1+y-1=k 即x+y=k-2，
此时最小块面积是floor(n/x)*floor(m/y),要使最小块面积最大，即使x*y尽量小。
x*y=x(k-2-x) = -x+(k-2)x，这是一个开头向下的抛物线，抛物线中间值最大，要是值x*y最小，x必须在抛物线的两边，x在0这边或者k这边。
现在分情况考虑
（1）如果k<n，这最优的(x,y)，是{x=1,y=k+1}（列切k次）或者{x=k+1, y=1}(行切k次)
（2）如果n≤k<m，这最优的(x,y)，是{x=1,y=k+1}(列切k次)
（3）如果m≤k≤n+m-2，最优的(x,y)，是{x=k+2-m,y=m}(行切k+1-m次，列切m次)
（4） 如果 k>n+m-2，则不存在切割方法（行最多切n-1次，列最多切m-1次）
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#define ll long long
using namespace std; int main(){
ll n,m,k;
cin >> n >> m >>k;
if(n > m) swap(n,m);
if(k < n) cout<<max(n*(m/(k+)),n/(k+)*m)<<endl;
else if(k>=n && k < m) cout<<n*(m/(k+))<<endl;
else if(k>=m && k <= n+m-) cout<<n/(k+-m)<<endl;
else cout<<-<<endl;
}
D - Jzzhu and Cities
题目的意思：
给你n个城市，m条无向有权边，然后还有k条边，每条边是从起点出发到i，以及相应的权重，删除这k条边中的一些边，使每个点到起点的最短距离不变。
解题思路是:
将原有的m条边和k条边都加入图中，注意要区分这两种不同的边，对于k条边是可以删除的，要进行标记。然后跑一遍dijkstra算法，记录其每个点最短路径的前一个点。然后遍历这些点，如果前一个点是起始点，且当前点到前一个点是可以删除边，则这条边不可以删除。
关于dijkstra算法，可以参考《算法竞赛入门经典训练指南》p327给的模板，这本书上面有很多模板写的比较好
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cstdlib>
#define ll long long
#define INF 0xffffffff
#define maxn 100000
using namespace std; struct Edge{
int from,to;
ll dist;
bool flag;
}; struct HeapNode{
ll d;
int u;
bool operator<(const HeapNode& rhs) const{
return d > rhs.d;
}
}; struct Dijkstra{
int n,m;
vector<Edge> edges;
vector<int> G[maxn];
bool done[maxn];
ll d[maxn];
int p[maxn]; void init(int n){
this->n = n;
for(int i = ; i < n ; ++ i) G[i].clear();
edges.clear();
} void AddEdge(int from, int to, int dist,bool flag = false){
edges.push_back((Edge){from,to,dist,flag});
m = edges.size();
G[from].push_back(m-);
} void dijkstra(int s){
priority_queue<HeapNode> Q;
for(int i = ; i < n; ++ i ) d[i] = INF;
d[s] = ;
memset(done,,sizeof(done));
Q.push((HeapNode){,s});
while(!Q.empty()){
HeapNode x = Q.top();Q.pop();
int u = x.u;
if(done[u]) continue;
done[u] = true;
for(int i = ; i < G[u].size(); ++ i){
Edge& e = edges[G[u][i]];
if(d[e.to] > d[u] + e.dist || (d[e.to] == d[u] + e.dist && !e.flag)){
d[e.to] = d[u] + e.dist;
p[e.to] = G[u][i];
Q.push((HeapNode){d[e.to], e.to});
}
}
}
}
}; int main(){
int n,m,k;
cin >> n >> m >> k;
Dijkstra a;
a.init(n);
for(int i = ; i < m; ++ i){
int u,v;
ll x;
cin >> u >> v >>x;
--u;--v;
a.AddEdge(u,v,x);
a.AddEdge(v,u,x);
}
for(int i = ; i < k; ++i){
int s;
ll y;
cin >>s >> y;
--s;
a.AddEdge(,s,y,true);
a.AddEdge(s,,y,true);
}
a.dijkstra();
int res = ;
for(int i = ; i < n; ++ i){
if(a.edges[a.p[i]].flag) res++;
}
cout<<k-res<<endl;
}
Dijkstra算法
E - Jzzhu and Apples
题目的意思：
有1到n个数，它们两两分为一组，要求在一组的数字的公共因子大于1，即要求这两个数不互质，问最多有多少分组
解题思路:
对于找出n以内的素数，由于n的最大为100000，可以考虑用筛选法选择素数。（其核心思想就是素数的倍数都不是素数）
2是素数，则2*2,2*3........都不是素数，然后将这些数标记，下一个数是3
3是素数，则3*2,3*3........都不是素数，然后将这些数标记，下一个数是5
.........
对于1和大于n/2的素数不可能满足要求，因为不可能存在一个在n内的数和大于n/2的素数有公因子
只需要考虑2到n/2范围内的素数。这里可能有疑问，为什么不考虑2到n/2的非素数？可以想象把筛选法筛选素数的方法逆过来。
假设i是2~n/2内的一个素数，那么2*i,3*i,4*i......(小于等于n)，有公因子i，
如果这些数的个数（包括i）为偶数的话，那么这些数两两组合即可
否则为奇数的话，选择2*i（i的偶数倍都可以），留给2的倍数去考虑，然后其余的两两组合
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <utility>
#define MAX (100000+5)
using namespace std; bool prime[MAX], visit[MAX];
void init(){
memset(prime,true,sizeof(prime));
memset(visit,false,sizeof(visit));
for(int i = ; i < MAX;++i){
if(prime[i]){
for(int j = i*;j < MAX; j+=i) prime[j] = false;
}
}
} int main(){
init();
int n;
cin >>n;
vector<pair<int,int> >res;
for(int i = n/; i>=; -- i){
if(prime[i]){
vector<int> divisor;
for(int j = i; j <= n; j+=i){
if(!visit[j]) divisor.push_back(j);
}
if(divisor.size()% != ){
for(int j = ; j < divisor.size(); ++ j){
if(divisor[j]% == ) {
swap(divisor[j],divisor.back());
divisor.pop_back();
break;
}
}
}
for(int j = ; j < divisor.size() ; j+=){
res.push_back(make_pair(divisor[j],divisor[j+]));
visit[divisor[j]] = true;
visit[divisor[j+]] = true;
}
}
}
cout<<res.size()<<endl;
for(int i = ; i < res.size(); ++i ) cout<<res[i].first<<" "<<res[i].second<<endl;
}