1.快速冪
題目描述
求 a 的 b 次方對 p 取模的值，其中 0≤a,b≤10^9 , 0<p≤10^9
輸入
三個用空格隔開的整數a,b和p，
輸出
一個整數，表示a^b mod p的值，
樣例輸入
2 3 9
樣例輸出
8
對于本題，按照以往的思路是直接回圈進行乘法，同時，邊乘邊取模，最終能夠得到結果，但是本題由于乘的次數過多導致運算時間過于長，所以要考慮的就是怎樣通過改進演算法來縮短計算時間
這里就有了快速冪，快速冪的目的就是快速求出冪，假設我們要求a^b,按照樸素演算法就是把a連乘b次，這樣一來時間復雜度是O(b)也即是O(n)級別，快速冪能做到O(logn)，快了好多好多，它的原理如下：
當冪指數非常大的時候，我們并沒有必要一次又一次的反復求，假設我們本來要求21024我們可以依次求得22、24、28、……21024這樣，原本需要1024次回圈，現在只用了10次，時間也就大大縮短了，
同理我們可以推進到一般情況，b可以拆解為若干不重復的2的次冪的和的形式，即可以用二進制的形式來表示，巧妙的運用位運算或者模運算，可以得到每一位前的系數為0或者1來達到快速冪的目的
#include<bits/stdc++.h>
using namespace std;
long long a,b,p;
long long f(long long a,long long b,long long p)
{
if(!p) return 0;
long long flag=1;
while(b)
{
if(b&1) flag=flag*a%p;
a=a*a%p;
b>>=1;
}
flag %=p;
return flag;
}
int main()
{
scanf("%lld%lld%lld",&a,&b,&p);
printf("%lld",f(a,b,p));
}
2.高精度乘法
題目描述
求a乘b對p取模的值，其中1≤a,b,p≤1018
輸入
輸入3個long long型整數，a,b,p
輸出
輸出a*b%p的值
樣例輸入
250182048980811753
413715569939057660
133223633696258584
樣例輸出
19308689043391716
對于本題，基本思想與第一題相同，只不過是將原本最終處理的乘法換為加法
#include<bits/stdc++.h>
using namespace std;
long long a,b,p;
long long f(long long a,long long b,long long p)
{
long long flag=0;
while(b)
{
if(b&1) flag=(flag+a)%p;
a=(a+a)%p;
b>>=1;
}
flag%=p;
return flag;
}
int main()
{
scanf("%lld%lld%lld",&a,&b,&p);
printf("%lld",f(a,b,p));
}
3.Raising Modulo Numbers
題目描述
People are different. Some secretly read magazines full of interesting girls’ pictures, others create an A-bomb in their cellar, others like using Windows, and some like difficult mathematical games. Latest marketing research shows, that this market segment was so far underestimated and that there is lack of such games. This kind of game was thus included into the KOKODáKH. The rules follow:
Each player chooses two numbers Ai and Bi and writes them on a slip of paper. Others cannot see the numbers. In a given moment all players show their numbers to the others. The goal is to determine the sum of all expressions AiBi from all players including oneself and determine the remainder after division by a given number M. The winner is the one who first determines the correct result. According to the players’ experience it is possible to increase the difficulty by choosing higher numbers.
You should write a program that calculates the result and is able to find out who won the game.
輸入
The input consists of Z assignments. The number of them is given by the single positive integer Z appearing on the first line of input. Then the assignements follow. Each assignement begins with line containing an integer M (1 <= M <= 45000). The sum will be divided by this number. Next line contains number of players H (1 <= H <= 45000). Next exactly H lines follow. On each line, there are exactly two numbers Ai and Bi separated by space. Both numbers cannot be equal zero at the same time.
輸出
For each assingnement there is the only one line of output. On this line, there is a number, the result of expression
(A1B1+A2B2+ … +AHBH)mod M.
樣例輸入
3
16
4
2 3
3 4
4 5
5 6
36123
1
2374859 3029382
17
1
3 18132
樣例輸出
2
13195
13
只要讀懂了本題的大概題意，就會發現這一題其實就是第一題的求和版，具體思路與第一題相同，將第一題的快速冪作為一個函式，每次輸入都運行一次這個函式最終求和取模就可以達到目的
#include<bits/stdc++.h>
using namespace std;
long long f(long long a,long long b,int m){
int flag=1;
while(b)
{
if(b&1) flag=flag*a%m;
a=a*a%m;
b>>=1;
}
flag%=m;
return flag;
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n;i++)
{
int m;
scanf("%d", &m);
int k;
scanf("%d", &k);
long long sum = 0;
for (int j = 0; j < k;j++)
{
long long a, b;
scanf("%lld %lld", &a, &b);
sum += f(a, b, m);
}
sum %= m;
printf("%lld\n", sum);
}
}
4.最短Hamilton路徑
題目描述
給定一張 n(n≤20) 個點的帶權無向圖，點從 0~n-1 標號，求起點 0 到終點 n-1 的最短Hamilton路徑， Hamilton路徑的定義是從 0 到 n-1 不重不漏地經過每個點恰好一次，
輸入
第一行一個整數n，
接下來n行每行n個整數，其中第i行第j個整數表示點i到j的距離（一個不超過10^7的正整數，記為a[i,j]），
對于任意的x,y,z，資料保證 a[x,x]=0，a[x,y]=a[y,x] 并且 a[x,y]+a[y,z]>=a[x,z]，
輸出
一個整數，表示最短Hamilton路徑的長度，
樣例輸入
4
0 2 1 3
2 0 2 1
1 2 0 1
3 1 1 0
樣例輸出
4
本題第一眼想到的演算法就是暴力演算法：就是列舉n個點的全排列，計算路徑長度的最小值，時間復雜程度為o（n*n!），而通過DP壓縮我們可以把時間縮短到o（n2*2n）.
在任意時刻如何表示哪些點已經被經過了呢？可以用一個n位的二進制數，如果它第i位為1，那么就表示第i個點已經被經歷過，反之則未經歷，同時我們還要知道當前的位置，所以就用一個二維陣列f[1 << 20][20]來表示狀態和位置，
下面我們列舉任意時刻的常規情況，可以得到一個遞推公式為：f[i][j] = min(f[i][j],f[i - (1 << j)][k] + weight[k][j])
舉個例子，例如當i等于11的時候，i的二進制表示為1011，i表示編號為0，1，3的人都已經走過了，我們就列舉當前位置，比如當前在1號位置，那么前一個狀態就是1001，我們可以從0號位，或者3號位走到1號位，也就是在前一個狀態中找到最小的出發點到1號位，
當每次走過這個位置的時候只需要通過位運算洗掉這個點就行了
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
int f[1 << 20][20]; //f[i][j]表示i的狀態，為1則代表經過，為0則代表沒經過，j代表當前所處的位置，
int weight[20][20];
int main()
{
int n;
cin >> n;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
cin >> weight[i][j];
memset(f, 0x3f, sizeof f);
f[1][0] = 0; //起點為0，i為1代表經過0這個起點，j為0代表當前在0這個位置
for(int i = 0; i < 1 << n; i++)
for(int j = 0 ; j < n; j++)
if(i >> j & 1){ //如果經過了第j位，則與上一狀態比較，尋找最小值
for(int k = 0; k < n; k++)
if(i - (1 << j) >> k & 1)//表示上一狀態沒有經過第j位，經過了第k位的情況
f[i][j] = min(f[i][j],f[i - (1 << j)][k] + weight[k][j]);}//取最小值
cout << f[(1 << n) - 1][n - 1] << endl;
return 0;
}
5.起床困難綜合征
題目描述
背景
21 世紀，許多人得了一種奇怪的病：起床困難綜合癥，其臨床表現為：起床難，起床后精神不佳，作為一名青春陽光好少年，atm 一直堅持與起床困難綜合癥作斗爭，通過研究相關文獻，他找到了該病的發病原因：在深邃的太平洋海底中，出現了一條名為 drd 的巨龍，它掌握著睡眠之精髓，能隨意延長大家的睡眠時間，正是由于 drd 的活動，起床困難綜合癥愈演愈烈，以驚人的速度在世界上傳播，為了徹底消滅這種病，atm 決定前往海底，消滅這條惡龍，
描述
歷經千辛萬苦，atm 終于來到了 drd 所在的地方，準備與其展開艱苦卓絕的戰斗，drd 有著十分特殊的技能，他的防御戰線能夠使用一定的運算來改變他受到的傷害，具體說來，drd 的防御戰線由 n扇防御門組成，每扇防御門包括一個運算op和一個引數t，其中運算一定是OR,XOR,AND中的一種，引數則一定為非負整數，如果還未通過防御門時攻擊力為x，則其通過這扇防御門后攻擊力將變為x op t，最終drd 受到的傷害為對方初始攻擊力x依次經過所有n扇防御門后轉變得到的攻擊力，
由于atm水平有限，他的初始攻擊力只能為0到m之間的一個整數（即他的初始攻擊力只能在0,1,…,m中任選，但在通過防御門之后的攻擊力不受 m的限制），為了節省體力，他希望通過選擇合適的初始攻擊力使得他的攻擊能讓 drd 受到最大的傷害，請你幫他計算一下，他的一次攻擊最多能使 drd 受到多少傷害，
輸入
第1行包含2個整數，依次為n,m，表示drd有n扇防御門，atm的初始攻擊力為0到m之間的整數，接下來n行，依次表示每一扇防御門，每行包括一個字串op和一個非負整數t，兩者由一個空格隔開，且op在前，t在后，op表示該防御門所對應的操作， t表示對應的引數，
n<=105，0<=m<=109，0<=t<=109 ，op一定為OR,XOR,AND 中的一種
輸出
一行一個整數，表示atm的一次攻擊最多使 drd 受到多少傷害，
樣例輸入
3 10
AND 5
OR 6
XOR 7
樣例輸出
1
本題看似復雜，不難發現位運算有基本規律，就是不會出現進位或者借位的現象，并且在二進制中只用兩種，即1或者0，我們就可以通過全為1和全為0的數位運算后得到的結果，從高到低，用每個引數的第k位進行位運算，運用貪心的思想，讓運算后的高位盡可能為1，同時原本的數不超過m的大小即可
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
int n,m;
cin>>n>>m;
int a0=0,a1=-1;
for(int i=1;i<=n;i++){
string s;
cin>>s;
int d;
cin>>d;
if(s[0]=='A')a1&=d,a0&=d;
if(s[0]=='O')a1|=d,a0|=d;
if(s[0]=='X')a1^=d,a0^=d;
}
ll ans=0;
for(int i=29;i>=0;i--){
if(a0>>i&1)ans+=1<<i;
else if((a1>>i&1)&&((1<<i)<=m))ans+=1<<i,m-=1<<i;
}
cout<<ans<<endl;
}
6.遞回性實作排列性列舉
題目描述
把 1~n 這 n(n<10) 個整數排成一行后隨機打亂順序，輸出所有可能的次序，
輸入
一個整數n，
輸出
按照從小到大的順序輸出所有方案，每行1個， 首先，同一行相鄰兩個數用一個空格隔開，其次，對于兩個不同的行，對應下標的數一一比較，字典序較小的排在前面，
樣例輸入
3
樣例輸出
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
這一題就是一個簡單的遞回問題，遞回，本質上來講就是每次都能夠套用相同的結局方式，假如給的只有兩個數，那么排列方式很簡單，加入有三個呢？我們把第一個固定，再求后兩個數的全排列，假如更多呢？如果有6個呢？那就先固定第一個求剩下的全排列，固定的這一個可能是第一個，也可能是第二個，第三個……，固定一個后再固定一個，以此類推，這樣就相當于可以套用相同的公式的遞回了，
#include<stdio.h>
int a[9]={0}, flag[10]={0};
int p(int c,int n){
if(c==n){
for (int i = 0; i < n;i++)
printf("%d ", a[i]);
printf("\n");
}
else{
for (int i = 1; i <= n;i++)
{
if(flag[i])
continue;
a[c] = i;
flag[i] = 1;
p(c + 1, n);
flag[i] = 0;
}
}
}
int main()
{
int n;
while(scanf("%d", &n)!=EOF)
p(0, n);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/251809.html
標籤：其他
上一篇：堆疊的動態分配相關功能的實作