轉(zhuǎn)圈游戲
題目
n 個(gè)小伙伴（編號(hào)從 0 到 n-1）圍坐一圈玩游戲跛蛋。按照順時(shí)針?lè)较蚪o n 個(gè)位置編號(hào)熬的，從0 到 n-1。最初赊级，第 0 號(hào)小伙伴在第 0 號(hào)位置押框，第 1 號(hào)小伙伴在第 1 號(hào)位置，……此衅，依此類推强戴。游戲規(guī)則如下：每一輪第 0 號(hào)位置上的小伙伴順時(shí)針走到第 m 號(hào)位置，第 1 號(hào)位置小伙伴走到第 m+1 號(hào)位置挡鞍，……骑歹，依此類推，第n ? m號(hào)位置上的小伙伴走到第 0 號(hào)位置墨微，第n-m+1 號(hào)位置上的小伙伴走到第 1 號(hào)位置道媚，……，第 n-1 號(hào)位置上的小伙伴順時(shí)針走到第m-1 號(hào)位置。
現(xiàn)在最域，一共進(jìn)行了 10^k輪谴分，請(qǐng)問(wèn) x 號(hào)小伙伴最后走到了第幾號(hào)位置。
輸入輸出格式
輸入格式：
輸入文件名為 circle.in镀脂。
輸入共 1 行牺蹄，包含 4 個(gè)整數(shù) n、m薄翅、k沙兰、x，每?jī)蓚€(gè)整數(shù)之間用一個(gè)空格隔開(kāi)翘魄。
輸出格式：
輸出文件名為 circle.out鼎天。
輸出共 1 行，包含 1 個(gè)整數(shù)暑竟，表示 10^k 輪后 x 號(hào)小伙伴所在的位置編號(hào)斋射。
樣例
樣例輸入
10 3 4 5
樣例輸出
5
說(shuō)明
數(shù)據(jù)范圍
對(duì)于 30%的數(shù)據(jù)，0 < k < 7但荤；
對(duì)于 80%的數(shù)據(jù)罗岖，0 < k < 10^7；
對(duì)于 100%的數(shù)據(jù)纱兑，1 <n < 1,000,000呀闻，0 < m < n，1 ≤ x ≤ n潜慎，0 < k < 10^9
思路
- 先通過(guò)草稿手動(dòng)模擬捡多，可以得到規(guī)律，最后的位置為（x+m*10^k)%n
- 很明顯铐炫，算m*10^k需要用到快速冪
- 數(shù)據(jù)范圍：為了防止爆long long要不斷%n
代碼
#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;
long long n;
long long pow(int root, int time) {
int ans=1;
while(time) {
if(time & 1) ans=(root*ans)%n;
root=(root*root)%n;
time>>=1;
}
return ans%n;
}
int main() {
long long m,k,x;
long long t,r;
cin>>n>>m>>k>>x;
r=0;
t=pow(10,k);
t*=m;
t%=n;
r=(x+t)%n;
cout<<r<<endl;
return 0;
}
火柴排隊(duì)
題目
涵涵有兩盒火柴垒手，每盒裝有 n 根火柴，每根火柴都有一個(gè)高度倒信。 現(xiàn)在將每盒中的火柴各自排成一列科贬， 同一列火柴的高度互不相同， 兩列火柴之間的距離定義為： ∑(ai-bi)^2
其中 ai 表示第一列火柴中第 i 個(gè)火柴的高度鳖悠，bi 表示第二列火柴中第 i 個(gè)火柴的高度榜掌。
每列火柴中相鄰兩根火柴的位置都可以交換，請(qǐng)你通過(guò)交換使得兩列火柴之間的距離最小乘综。請(qǐng)問(wèn)得到這個(gè)最小的距離憎账，最少需要交換多少次？如果這個(gè)數(shù)字太大卡辰，請(qǐng)輸出這個(gè)最小交換次數(shù)對(duì) 99,999,997 取模的結(jié)果胞皱。
輸入輸出
輸入：
輸入文件為 match.in邪意。
共三行，第一行包含一個(gè)整數(shù) n反砌，表示每盒中火柴的數(shù)目雾鬼。
第二行有 n 個(gè)整數(shù)，每?jī)蓚€(gè)整數(shù)之間用一個(gè)空格隔開(kāi)宴树，表示第一列火柴的高度策菜。
第三行有 n 個(gè)整數(shù)，每?jī)蓚€(gè)整數(shù)之間用一個(gè)空格隔開(kāi)森渐，表示第二列火柴的高度做入。
輸出：
輸出文件為 match.out。
輸出共一行同衣，包含一個(gè)整數(shù)，表示最少交換次數(shù)對(duì) 99,999,997 取模的結(jié)果
思路
- 先來(lái)證明一個(gè)公式：
若a1>a2且b1>b2壶运，則有(a1-b1)^2 +(a2-b2)^2 < (a2-b1)^2 + (a1-b2)^2
當(dāng)然這個(gè)公式很容易證耐齐，拆開(kāi)就好了- 然后運(yùn)用這個(gè)公式，發(fā)現(xiàn)為保證火柴距離最小蒋情，兩列火柴對(duì)應(yīng)的兩根火柴在各列中高度的排名應(yīng)該相同
- 再來(lái)定義一個(gè)r數(shù)組埠况，使得r[a[i].num]=b[i].num,則可以很驚奇地發(fā)現(xiàn)，交換次數(shù)即為r數(shù)組中逆序?qū)Φ膫€(gè)數(shù)棵癣，此題得解
現(xiàn)在考慮求逆序?qū)?/strong>
用歸并排序求：
實(shí)際上歸并排序的交換次數(shù)就是這個(gè)數(shù)組的逆序?qū)€(gè)數(shù)辕翰，為什么呢？
- 歸并排序是將數(shù)列a[l,h]分成兩半a[l,mid]和a[mid+1,h]分別進(jìn)行歸并排序狈谊，然后再將這兩半合并起來(lái)喜命。
- 在合并的過(guò)程中（設(shè)l<=i<=mid，mid+1<=j<=h）河劝，當(dāng)a[i]<=a[j]時(shí)壁榕，并不產(chǎn)生逆序數(shù)；當(dāng)a[i]>a[j]時(shí)赎瞎，在
- 前半部分中比a[i]大的數(shù)都比a[j]大牌里，將a[j]放在a[i]前面的話，逆序數(shù)要加上mid+1-i务甥。因此牡辽，可以在歸并排序中的合并過(guò)程中計(jì)算逆序數(shù).
用樹(shù)狀數(shù)組求：
- 每輸入一個(gè)b[i],就用a[b[i]+1]++去標(biāo)記總共輸入多少次了（因?yàn)檩斎氲臄?shù)據(jù)是0~n-1，所以輸入的b[i]就相當(dāng)于a[i]的下標(biāo)i敞临，而且有0态辛，樹(shù)狀數(shù)組無(wú)法對(duì)下標(biāo)為0進(jìn)行操作，所以要a[b[i]+1]）;
- 對(duì)于一個(gè)b[i],要想查詢它前面有多少大于它的哟绊，只需將a[b[i]+1]到a[n]加起來(lái)因妙，也就是求一段數(shù)組的和痰憎，那么樹(shù)狀數(shù)組就上場(chǎng)加速了
代碼
歸并排序
#include<cstdio>
#include<algorithm>
using namespace std;
typedef struct n{
int num,ord;
}node;
node first_team[100010],second_team[100010];
int a[100010],b[100010],ans;
int compare(node x,node y)
{
return x.num<y.num;
}
void Merge(int l,int r)
{
if(l>=r) return ;
int mid=(l+r)/2;
Merge(l,mid);
Merge(mid+1,r);
int i=l,j=mid+1,k=l;
while(i<=mid&&j<=r)
{
if(a[i]>a[j])
{
b[k++]=a[j++];
ans+=mid-i+1;
ans%=99999997;
}
else b[k++]=a[i++];
}
while(i<=mid) b[k++]=a[i++];
while(j<=r) b[k++]=a[j++];
for(int i=l;i<=r;i++)
a[i]=b[i];
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&first_team[i].num);
first_team[i].ord=i;
}
for(int i=1;i<=n;i++)`
{
scanf("%d",&second_team[i].num);
second_team[i].ord=i;
}
sort(first_team+1,first_team+n+1,compare);
sort(second_team+1,second_team+n+1,compare);
for(int i=1;i<=n;i++)
a[first_team[i].ord]=second_team[i].ord;
Merge(1,n);
printf("%d",ans);
return 0;
}
樹(shù)狀數(shù)組
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 100010;
const int maxm = 99999997;
struct MyStruct
{
int data;
int loc;
}a[maxn],b[maxn];
int e[maxn], n, c[maxn];
int inline readint()
{
int x = 0;
char c = getchar();
while (c<'0' || c>'9') c = getchar();
while (c >= '0'&&c <= '9')
{
x = x * 10 + c - '0';
c = getchar();
}
return x;
}
int lowbit(int x)
{
return x&-x;//樹(shù)狀數(shù)組實(shí)現(xiàn)
}
void add(int x,int t)
{
while (x <= n)
{
e[x] += t;
e[x] %= maxm;
x += lowbit(x);//每次往后加，可以改變后面對(duì)應(yīng)的和
}
}
int sum(int x)
{
int s = 0;
while(x)
{
s += e[x];
s %= maxm;
x -= lowbit(x);//得到所求的和
}
return s;
}
bool cmp(MyStruct x, MyStruct y)
{
return x.data < y.data;
}
int main()
{
n = readint();
for (int i = 1; i <= n; i++)
{
a[i].data = readint();
a[i].loc = i;//記錄位置
}
for (int i = 1; i <= n; i++)
{
b[i].data = readint();
b[i].loc = i;
}
sort(a + 1, a + n + 1, cmp);
sort(b + 1, b + n + 1, cmp);
for (int i = 1; i <= n; i++)
{
c[a[i].loc] = b[i].loc;//離散優(yōu)化
}
int ans = 0;
for (int i = 1; i <= n; i++)
{
add(c[i], 1);//離散優(yōu)化后大小就是正確順序的位置
ans += i - sum(c[i]);//當(dāng)前位置攀涵，減去之前比他大的數(shù)的個(gè)數(shù)
ans %= maxm;
}
printf("%d", ans);
return 0;
}
積木大賽
題目
春春幼兒園舉辦了一年一度的“積木大賽”铣耘。今年比賽的內(nèi)容是搭建一座寬度為n的大廈，大廈可以看成由n塊寬度為1的積木組成以故，第i塊積木的最終高度需要是hi蜗细。
在搭建開(kāi)始之前，沒(méi)有任何積木（可以看成n塊高度為 0 的積木）怒详。接下來(lái)每次操作炉媒，小朋友們可以選擇一段連續(xù)區(qū)間[l, r]，然后將第第 L 塊到第 R 塊之間（含第 L 塊和第 R 塊）所有積木的高度分別增加1昆烁。
小 M 是個(gè)聰明的小朋友吊骤，她很快想出了建造大廈的最佳策略，使得建造所需的操作次數(shù)最少静尼。但她不是一個(gè)勤于動(dòng)手的孩子白粉，所以想請(qǐng)你幫忙實(shí)現(xiàn)這個(gè)策略，并求出最少的操作次數(shù)鼠渺。
輸入輸出格式
輸入格式：
輸入文件為 block.in
輸入包含兩行鸭巴，第一行包含一個(gè)整數(shù)n，表示大廈的寬度拦盹。
第二行包含n個(gè)整數(shù)鹃祖，第i個(gè)整數(shù)為hi 。
輸出格式：
輸出文件為 block.out
僅一行普舆，即建造所需的最少操作數(shù)恬口。
輸入輸出樣例
樣例輸入
5
2 3 4 1 2
樣例輸出
5
思路
其實(shí)就是簡(jiǎn)單的貪心，觀察樣例奔害；
a[1]=2 所以位置1一定被操作了兩次 ans+=2
a[2]-a[1]=1 位置2比位置1多操作一次 ans+=1
但a[i]<a[i-1]時(shí)楷兽，跳過(guò)。因?yàn)閷?duì)于a[i]<a[i-1]的情況华临，a[i]和a[i-1]一定不在一次操作內(nèi)
以此類推芯杀，就得到最后的答案
代碼
/*很簡(jiǎn)短*/
#include<iostream>
#include<cstdio>
#define MAXX 100000+5
using namespace std;
int a[MAXX],n;
long long ans=0;
int main() {
scanf("%d",&n);
for (int i=1; i<=n; i++) {
scanf("%d",&a[i]);
if (a[i]>a[i-1]) ans+=a[i]-a[i-1];
}
printf("%lld",ans);
return 0;
}
貨車運(yùn)輸
題目描述
A 國(guó)有 n 座城市，編號(hào)從 1 到 n雅潭，城市之間有 m 條雙向道路揭厚。每一條道路對(duì)車輛都有重量限制，簡(jiǎn)稱限重》龉現(xiàn)在有 q 輛貨車在運(yùn)輸貨物筛圆， 司機(jī)們想知道每輛車在不超過(guò)車輛限重的情況下，最多能運(yùn)多重的貨物椿浓。
輸入輸出
輸入格式：
輸入文件名為 truck.in太援。
輸入文件第一行有兩個(gè)用一個(gè)空格隔開(kāi)的整數(shù) n闽晦，m，表示 A 國(guó)有 n 座城市和 m 條道路提岔。 接下來(lái) m 行每行 3 個(gè)整數(shù) x仙蛉、 y、 z碱蒙，每?jī)蓚€(gè)整數(shù)之間用一個(gè)空格隔開(kāi)荠瘪，表示從 x 號(hào)城市到 y 號(hào)城市有一條限重為 z 的道路。注意： x 不等于 y赛惩，兩座城市之間可能有多條道路 哀墓。
接下來(lái)一行有一個(gè)整數(shù) q，表示有 q 輛貨車需要運(yùn)貨喷兼。
接下來(lái) q 行篮绰，每行兩個(gè)整數(shù) x、y褒搔，之間用一個(gè)空格隔開(kāi)阶牍，表示一輛貨車需要從 x 城市運(yùn)輸貨物到 y 城市，注意： x 不等于 y 星瘾。
輸出格式：
輸出文件名為 truck.out。
輸出共有 q 行惧辈，每行一個(gè)整數(shù)琳状，表示對(duì)于每一輛貨車，它的最大載重是多少盒齿。如果貨車不能到達(dá)目的地念逞，輸出-1。
輸入輸出樣例
輸入樣例：
4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3
輸出樣例#1：
3
-1
3
說(shuō)明
數(shù)據(jù)范圍
對(duì)于 30%的數(shù)據(jù)边翁，0 < n < 1,000翎承，0 < m < 10,000，0 < q< 1,000符匾；
對(duì)于 60%的數(shù)據(jù)叨咖，0 < n < 1,000，0 < m < 50,000啊胶，0 < q< 1,000甸各；
對(duì)于 100%的數(shù)據(jù)，0 < n < 10,000焰坪，0 < m < 50,000趣倾，0 < q< 30,000，0 ≤ z ≤ 100,000某饰。
思路
- 求一條路徑的最小邊的最大值儒恋，符合該條件的路徑一定在最大生成樹(shù)上
- 在最大生成樹(shù)上跑LCA倍增善绎。即求起點(diǎn)到LCA上最小邊和終點(diǎn)到LCA上最小邊的最小值
代碼
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;
const int inf = 100001;
const int maxn = 10010;
const int maxm = 50050;
int n, m, q, tot;
int st[maxn], vis[maxn], deep[maxn], fa[maxn][17], g[maxn][17], f[maxn];
struct node{
int v, w, next;
} edge[maxm];
struct node1{
int u, v, w;
} a[maxm];
bool cmp(node1 x, node1 y){
return x.w > y.w;
}
void in(int x, int y, int z){
edge[++tot].v = y;
edge[tot].w = z;
edge[tot].next = st[x];
st[x] = tot;
}
void init(){
for(int i = 1; i <= n; i++) f[i] = i;
memset(fa, 0, sizeof(fa));
memset(g, 0, sizeof(g));
}
int find(int x){
if(f[x] == x) return x;
return f[x] = find(f[x]);
}
void kruskal(){
init();
for(int i = 1, from, to, ff, ft; i <= m; i++){
from = a[i].u, to = a[i].v;
ff = find(from), ft = find(to);
if(ff != ft){
f[ff] = ft;
in(from, to, a[i].w);
in(to, from, a[i].w);
}
}
}
void dfs(int rt){//建樹(shù)
vis[rt] = 1;
for(int i = 1; i <= 16; i++){
if(deep[rt] < (1<<i)) break;
fa[rt][i] = fa[fa[rt][i-1]][i-1];
g[rt][i] = min(g[rt][i-1], g[fa[rt][i-1]][i-1]);
}
for(int i = st[rt]; i; i = edge[i].next){
int to = edge[i].v;
if(vis[to]) continue;
fa[to][0] = rt;
g[to][0] = edge[i].w;
deep[to] = deep[rt] + 1;
dfs(to);
}
}
int lca(int x, int y){//倍增往上跳，返回最近公共祖先
if(deep[x] < deep[y]) swap(x, y);
int delta = deep[x] - deep[y];
for(int i = 0; i <= 16; i++)//2^16正好過(guò)50000
if(delta & (1<<i)) x = fa[x][i];
for(int i = 16; i >= 0; i--)
if(fa[x][i] != fa[y][i]){
x = fa[x][i];
y = fa[y][i];
}
if(x == y) return x;
else return fa[x][0];
}
int ask(int x, int y){//詢問(wèn)路上滿足條件的邊
int mn = inf;
int delta = deep[x] - deep[y];
for(int i = 0; i <= 16; i++)
if(delta & (1<<i)){
mn = min(mn, g[x][i]);
x = fa[x][i];
}
return mn;
}
int main(){
cin >> n >> m;
for(int i = 1, x, y, z; i <= m; i++)
cin >> a[i].u >> a[i].v >> a[i].w;
sort(a+1, a+m+1, cmp);
kruskal();
for(int i = 1; i <= n; i++)
if(!vis[i]) dfs(i);
cin >> q;
while(q--){
int op, ed;
cin >> op >> ed;
if(find(op) != find(ed)){
cout << "-1" << endl;
continue;
}
else{
int baba = lca(op, ed);
cout << min(ask(op, baba), ask(ed, baba)) << endl;
}
}
return 0;
}
花匠
題目
花匠棟棟種了一排花诫尽，每株花都有自己的高度禀酱。花兒越長(zhǎng)越大箱锐，也越來(lái)越擠比勉。棟棟決定把這排中的一部分花移走，將剩下的留在原地驹止，使得剩下的花能有空間長(zhǎng)大浩聋，同時(shí)，棟棟希望剩下的花排列得比較別致臊恋。
具體而言衣洁，棟棟的花的高度可以看成一列整數(shù)h1,h2..hn。設(shè)當(dāng)一部分花被移走后抖仅，剩下的花的高度依次為g1,g2..gn坊夫，則棟棟希望下面兩個(gè)條件中至少有一個(gè)滿足：
條件 A：對(duì)于所有g(shù)(2i)>g(2i-1),g(2i)>g(2i+1)
條件 B：對(duì)于所有g(shù)(2i)<g(2i-1),g(2i)<g(2i+1)
注意上面兩個(gè)條件在m = 1時(shí)同時(shí)滿足，當(dāng)m > 1時(shí)最多有一個(gè)能滿足撤卢。
請(qǐng)問(wèn)环凿，棟棟最多能將多少株花留在原地。
輸入輸出格式
輸入格式：
輸入文件為 flower .in放吩。
輸入的第一行包含一個(gè)整數(shù)n智听，表示開(kāi)始時(shí)花的株數(shù)。
第二行包含n個(gè)整數(shù)渡紫，依次為h1,h2..hn,表示每株花的高度到推。。
輸出格式：
輸出文件為 flower .out惕澎。
輸出一行莉测，包含一個(gè)整數(shù)m，表示最多能留在原地的花的株數(shù)唧喉。
輸入輸出樣例
樣例輸入
5
5 3 2 1 2
樣例輸出
3
說(shuō)明
樣例解釋
有多種方法可以正好保留 3 株花，例如欣喧，留下第 1腌零、4、5 株唆阿，高度分別為 5益涧、1、2驯鳖，滿足條件 B闲询。
數(shù)據(jù)范圍
對(duì)于 20%的數(shù)據(jù)久免，n ≤ 10；
對(duì)于 30%的數(shù)據(jù)扭弧，n ≤ 25阎姥；
對(duì)于 70%的數(shù)據(jù)，n ≤ 1000鸽捻，0 ≤ ?i≤ 1000呼巴；
對(duì)于 100%的數(shù)據(jù)，1 ≤ n ≤ 100,000御蒲，0 ≤ hi≤ 1,000,000衣赶，所有的hi 隨機(jī)生成，所有隨機(jī)數(shù)服從某區(qū)間內(nèi)的均勻分布厚满。
思路
意思就是讓你找轉(zhuǎn)折點(diǎn)的數(shù)量即g(i-1)<gi>g(i+1)或g(i-1)>gi<g(i+1)府瞄，gi即是轉(zhuǎn)折點(diǎn)。首先可以肯定的是碘箍，當(dāng)花的數(shù)目為1的時(shí)候遵馆，可以直接輸出1。首尾兩株花都肯定是可以留下的丰榴，因此货邓，當(dāng)花的數(shù)目大于等于2時(shí)，我們可以將答案初始化為2四濒，然后加上轉(zhuǎn)折點(diǎn)的數(shù)目即可
代碼
#include<iostream>
#include<cstdio>
using namespace std;
int a[100005];
int w,n,ans;
int main(){
scanf("%d",&n);
a[0]=-147258963;
for(int i=1;i<=n;i++){
scanf("%d",&a[++w]);
if(a[w]==a[w-1]) --w;
}
if(w==1) {
printf("1");
return 0;
}
ans=2;
for(int i=2;i<=w-1;i++){
if (((a[i]>a[i-1])&&(a[i]>a[i+1]))||((a[i]<a[i-1])&&(a[i]<a[i+1]))){
ans++;
}
}
printf("%d",ans);
return 0;
}
