比賽連結：點我
連結：https://www.nowcoder.com/acm/contest/185/A
來源：牛客網
題目描述
給出一個二進制組（A,B）
求出無序二進制組（a,b） 使得（a|A，b|B）的組數
無序意思就是(a,b)和(b,a) 算一組.
輸入描述:
第一行資料組數 T（1≤T≤10000）
接下來T行，每行兩個正整數 A,B（1≤A,B≤10000）
輸出描述:
共T行，每行一個結果
組合，求A和B的因子個數，乘起來，減去他們最大公約數的因子的組合數，組合數為n*(n-1)/2
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 7;
int num[maxn];
int count(int n)///求因子的個數
{
int s=1;///記錄總共的素因子的個數
for(int i=2;i*i<=n;i++)
if(n%i==0)
{
int a=0;///記錄的是每個素因子的個數
while(n%i==0)
{
n/=i;
a++;
}
s=s*(a+1);
}
if(n>1)
s=s*2;
return s;
}
int main(){
for(int i = 1; i < maxn; i++) {
for(int j = i; j < maxn; j += i)
num[j]++;
}//一種求因子的方法
int T, a, b;
scanf("%d", &T);
while(T--) {
scanf("%d%d", &a, &b);
int t = __gcd(a, b);
printf("%lld\n", 1ll * count(a) * count(b) - 1ll*(count(t) - 1) * count(t) / 2);
}
return 0;
}
連結：https://www.nowcoder.com/acm/contest/185/B
來源：牛客網
題目描述
給出一個 n * n 的鄰接矩陣A.
A是一個01矩陣 .
A[i][j]=1表示i号點和j号點之間有長度為1的邊直接相連.
求出從 1 号點 到 n 号點長度為k的路徑的數目.
輸入描述:
第1行兩個數n,k (20 ≤n ≤ 30,1 ≤ k ≤ 10)
第2行至第n+1行，為一個鄰接矩陣
輸出描述:
題目中所求的數目
離散數學題，矩陣自乘k次就能知道幾号點到幾号點的長度為k的路徑有幾條
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MA 50
typedef long long ll;
ll G[MA][MA], mu[MA][MA], g[MA][MA];
int main(){
int n, m;
int i, j, k;
ll num;
scanf("%d%d",&n,&m);
for(i=0; i<n; i++){
for(j=0; j<n; j++){
scanf("%lld", &G[i][j]);
g[i][j] = G[i][j];
}
}
while(--m){
memset( mu, 0, sizeof(mu));
for(i=0; i<n; i++){
for(j=0; j<n; j++){
for(k=0; k<n; k++){
mu[i][j] += g[i][k] * G[k][j];
}
}
}
for(i=0; i<n; i++){
for(j=0; j<n; j++){
G[i][j] = mu[i][j];
}
}
}
num = 0;
num=G[0][n-1];
printf("%lld\n",num);
return 0;
}
連結：https://www.nowcoder.com/acm/contest/185/C
來源：牛客網
題目描述
給出一個數列 A，求出一個數列B.
其中Bi 表示 數列A中 Ai 右邊第一個比 Ai 大的數的下标(從1開始計數),沒有找到這一個下标 Bi 就為0
輸出數列B
輸入描述:
第一行1個數字 n (n ≤ 10000)
第二行n個數字第 i 個數字為 Ai (0 ≤ Ai ≤ 1000000000)
輸出描述:
一共一行，第 i 個數和第 i+1 個數中間用空格隔開.
暴力
#include<iostream>
#include<cstdio>
using namespace std;
const int N=10000+100;
int a[N];
int b[N];
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
int num;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(a[j]>a[i]){
b[i]=j+1;
break;
}
}
}
for(int i=0;i<n;i++){
if(i!=n-1){
printf("%d ",b[i]);
}
else{
printf("%d",b[i]);
}
}
}
連結：https://www.nowcoder.com/acm/contest/185/D
來源：牛客網
題目描述
Johnson和Nancy要在星光下吃晚餐。這是一件很浪漫的事情。
為了增加星光晚餐那浪漫的氛圍，他拿出了一個神奇的魔法棒，并且可以按照一定的規則，改變天上星星的亮暗。
Johnson想考考Nancy，在他揮動魔法棒後，會有多少顆星星依舊閃耀在天空。他知道，Nancy一定會一口說出答案。
Nancy當然知道怎麼做啦，但她想考考你！
Johnson先将天上n個星星排成一排，起初它們都是暗的。
他告訴他的妹子，他将揮動n次魔法棒，第i次揮動會将編号為i的正整數倍的星星的亮暗反轉，即亮的星星轉暗，暗的星星轉亮。
Johnson想問Nancy，最終會有多少個星星依舊閃亮在天空。
輸入描述:
一個整數n，含義請見題目描述。
輸出描述:
一個整數ans，即n次操作後會有多少個星星依舊閃亮。
這個題知道真相的我眼淚掉下來，因為隻有因子個數為奇數的才亮，然後隻有完全平方數有奇數個因子，推導詳見：傳送門
#include<cstdio>
#include<cmath>
long long n;
int main()
{
scanf("%lld",&n);
printf("%lld",(long long)(sqrt(n)));
}
連結：https://www.nowcoder.com/acm/contest/185/E
來源：牛客網
題目描述
給定括号長度N，給出一串括号（隻包含小括号），計算出最少的交換（兩兩交換）次數，使整個括号序列比對。
我們認為一個括号比對，即對任意一個’)’，在其左側都有一個’('與它比對，且他們形成一一映射關系。
輸入描述:
第一行：整數N，表示括号序列長度
第二行：一個字元串，表示括号
輸出描述:
一個整數，表示最少的交換次數
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e6 + 10;
char s[N];
int n;
int main() {
scanf("%d%s", &n, s + 1);
int cnt = 0;
for(int i = 1 ; i <= n ; ++ i) {
if(s[i] == '(') ++ cnt;
else {
if(cnt) -- cnt;
}
}
printf("%d\n", (cnt+1)/ 2 );
}
連結：https://www.nowcoder.com/acm/contest/185/F
來源：牛客網
題目描述
輸入一個整數X，求一個整數N，使得N!恰好大于XX。
輸入描述:
第一行：一個整數X
輸出描述:
第一行：一個整數N
備注:
每個測試點所對應的X滿足：
第i個測試點輸入的值為第i-1個測試點輸入的值乘以10再加上7。
特别的，第一個測試點所輸入的值為7。
提示：資料共有10組。
我就是斯特林公式打表，然後可能寫錯了，打表失敗，算了直接貼大佬的二分算了
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const double pi = acos(-1), e = exp(1.0);
ll x;
double up;
bool check(double n){
return 0.5 * log(2 * pi * n) + n * log(n / e) >= up;
}
int main() {
scanf("%lld",&x);
up = x * log(x);
int times = 51;
double l = 1, r = 1e13, ans;
while(times--) {
ll mid = (l + r) / 2;
if(check(mid)) ans = mid, r = mid;
else l = mid;
}
cout <<(long long )ans;
return 0;
}
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int main()
{
long long x;
cin>>x;
long long l=x,r=x*3,mid;
while (l<r)
{
mid=(l+r)/2;
if (log(mid*1.0)*mid-mid+log(x)-1<x*log(x))
{
l=mid+1;
}
else
{
r=mid;
}
}
cout<<l;
return 0;
}
![常用刷題網址——提高代碼能力[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)