nnuJacob

nnu

512

nnuJacob
19天前
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = (1 << 20)+ 10;
int primes[N]; // primes[i]：第i个素数
int minP[N];   // minP[i]：i的最小质因子
bool st[N];
int cnt = 0;
int n;

void get_primes(int n){ // O(n)

for(int i = 2; i <= n; i++) {
if(!st[i]) // 没被筛掉，说明i是个素数
primes[cnt++] = i, minP[i] = i;
for(int j = 0; primes[j]*i < n; j++) {
st[primes[j]*i] = true;        // 用primes[j]把primes[j]*i筛掉，且只筛一次，即该合数的最小质因子是primes[j]，该条语句只执行一次！
minP[primes[j]*i] = primes[j]; // primes[j]*i的最小质因子是primes[j]
if(i % primes[j] == 0)         // primes[j]是i的最小素因数
break;
}
}
}

int sum[N]; // 记录每个素因子出现的次数
long long product[30];

int main(int argc, char** argv) {
// 存素数
get_primes(N);

// 存阶乘
product[1] = 1;
for(int i = 2; i <= 20; i++){
product[i] = product[i-1]*i;
}

int x;
while(scanf("%d",&x) != EOF){
//      memset(sum, 0, sizeof(sum)); 导致超时，数组长度10^6, 1^2组就超时
int tot = 0;
int pcnt = 0;
while(x > 1){
int mp = minP[x];
sum[pcnt] = 0;
while(x % mp == 0){
sum[pcnt]++;
tot++;
x /= mp;
}
pcnt++;
}
long long res = product[tot];
for(int i = 0; i < pcnt; i++){
res /= product[sum[i]];
}
printf("%d %lld\n",tot, res);
}
return 0;
}



nnuJacob
21天前
#include <iostream>
#include <cstdio>
#include <cstdarg>
#include <algorithm>
#include <cmath>
using namespace std;

int get_delt(){// 飞机起降当地时间差 (s)
int h1,h2,m1,m2,s1,s2;
int d=0;
scanf("%d:%d:%d %d:%d:%d (+%d)", &h1, &m1, &s1, &h2, &m2, &s2, &d);
return (d*24 + h2 - h1)*3600 + (m2-m1)*60 + s2-s1;
}

int main(){
int t;
cin >> t;
while(t--){
int t1 = get_delt();
int t2 = get_delt();

int delt = min(t1,t2) + fabs(t1 - t2)/2;
int h = delt/3600;
int m = (delt/60) % 60;
int s = delt%60;

printf("%02d:%02d:%02d\n", h, m, s);
}
system("pause");
return 0;
}


nnuJacob
21天前
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 100005;

struct She{
int time,id;
bool operator <(const She &other){
if(id != other.id) return id < other.id;
return time < other.time;
}
}s[N];

int n,m,t;
int res;

int main(){
cin >> n >> m >> t;
for(int i = 0 ; i < m; i++) scanf("%d %d", &s[i].time, &s[i].id);
// 1. 按照编号、时间排序
sort(s,s+m);
int cur_id = s[0].id; // 当前处理的id
int level = 2;
bool pri = false;
for(int i = 1; i < m; i++){
if(cur_id != s[i].id){ // id改变
// 查看上个id，T时刻是否优先
level = level - (t-s[i-1].time);
if(level <= 3) pri = false;
if(pri) res++;
cur_id = s[i].id, level = 2, pri = false; // 更新id
}
else{ // 同一个id
int delt = s[i].time - s[i-1].time;
if(delt > 1){ // 优先级可能降低
level = level - (delt-1); // 降低优先级
if(level < 0) level = 0;  // 最低为0
if(level <= 3) pri = false;
level += 2;               // 优先级增2
if(level > 5) pri = true;
}
else{ // 优先级增加
level += 2;
if(level > 5) pri = true;
}
}
}
// 单独查看最后一个外卖店T时刻是否优先，因为没有下一个订单了
level = level - (t-s[m-1].time);
if(level <= 3) pri = false;
if(pri) res++;
cout << res;
system("pause");
return 0;
}



nnuJacob
23天前
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int a, b, c;
int cnt = 0;
int year, month, day;

struct Date{
int y, m, d;
bool operator < (Date &t){
if(y != t.y) return y < t.y;
if(m != t.m) return m < t.m;
if(d != t.d) return d < t.d;
}
}date[3];

bool is_leap(int  x){
return x%4 == 0 && x%100 != 0 || x%400 == 0;
}
int get_year(int y){
if(y > 59) return 1900+y;
else return 2000+y;
}
int get_month(int m){
if(m < 1 || m > 12) return 0;
return m;
}
int get_day(int y, int m, int x){
if(m != 2) {
if(x < 1 || x > days[m])
return 0;
else
return x;
}
else{ // m == 2
if(x < 1 || x > 28+is_leap(y))
return 0;
else
return x;
}
}

bool exist(int y, int m, int d){
if(!cnt) return false;
for(int i = 0 ; i < cnt; i++){
if(date[i].d == d && date[i].m == m && date[i].y == y)
return true;
}
return false;
}

int main(){
string str;
cin >> str;
a = (str.at(0)-'0') * 10 + str.at(1)-'0';
b = (str.at(3)-'0') * 10 + str.at(4)-'0';
c = (str.at(6)-'0') * 10 + str.at(7)-'0';
// cout << a << " " << b << " " << c << endl;
year = get_year(a);
month = get_month(b);
day= get_day(a,b,c);
if(year && month && day && !exist(year, month, day)) {
date[cnt++] = {year, month, day};
}
year = get_year(c);
month = get_month(a);
day = get_day(c,a,b);
if(year && month && day && !exist(year, month, day)) {
date[cnt++] = {year, month, day};
}
year = get_year(c);
month = get_month(b);
day = get_day(c,b,a);
if(year && month && day && !exist(year, month, day)) {
date[cnt++] = {year, month, day};
}
sort(date, date+cnt);
// cout <<  cnt << endl;
for(int i = 0 ; i < cnt; i++){
cout << date[i].y << "-";
if(date[i].m < 10 ) cout << "0";
cout << date[i].m << "-";
if(date[i].d < 10 ) cout << "0";
cout << date[i].d << endl;
}

system("pause");
return 0;
}


nnuJacob
24天前
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int w, m, n;

int get_row(int x){
return x/w;
}
int get_col(int x){
int row = get_row(x);

if(row % 2 == 0) // 正序
if(row * w == x) return 0;
else return x - row*w;
else // 倒序列
if(row * w == x) return w-1;
else return w + 1 - (x - row*w);
}

int main(){

cin >> w >> m >> n;
int rowm = get_row(m);
int colm = get_col(m);
int rown = get_row(n);
int coln = get_col(n);
// cout << rowm << " " << colm << endl;
// cout << rown << " " << coln << endl;
cout << fabs(rowm - rown) + fabs(coln- colm);
return 0;
}



nnuJacob
28天前
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define INF 0xfffffff

const int N = 100005;
int a[N];
int delt[N];
int n;

int gcd(int a, int b){
return b==0 ? a : gcd(b,a%b);
}

int main(int argc, char** argv) {
cin >> n;
for(int i = 0; i < n; i++) {
scanf("%d",a+i);
}
sort(a,a+n);
int g = a[1] - a[0];
for(int i = 1; i < n; i++){
g = gcd(g, a[i] - a[i-1]);
}
if(a[n-1] - a[0])
cout << (a[n-1] - a[0])/g + 1;
else
cout << n;
return 0;
}


nnuJacob
28天前
#include <iostream>
#include <cstdio>
using namespace std;

const int N = 100005;
int a[N];
int tmp[N];
int n;
long long ans;

void merge_sort(int left, int right){
// 1. 边界
if(left >= right) return;

// 2. 划分子问题
int mid  = left+right >> 1;
merge_sort(left, mid);
merge_sort(mid+1, right);

// 3. 合并子问题

// 3.1
int i = left;
int j = mid+1;
int k = 0;
while(i <= mid && j <= right)
if(a[i] <= a[j])  tmp[k++] = a[i++];
else tmp[k++] = a[j++], ans += mid-i+1;
while(i <= mid) tmp[k++] = a[i++]; // 若执行，则j=right+1
while(j <= right) tmp[k++] = a[j++];

// 3.2
for(i = left, j = 0; i <= right; i++, j++) a[i] = tmp[j];

//

}
int main(int argc, char** argv) {
cin >> n;
for(int i = 0; i < n; i++) scanf("%d", a+i);
merge_sort(0, n-1);
cout << ans;
return 0;
}


nnuJacob
28天前
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 100005;
int n;
int a[N], tmp[N];

void merge_sort(int left, int right){

// 1. 边界
if(left >= right) return ;

// 2. 分治子问题：a分为左右
int mid = left+right >> 1;
merge_sort(left, mid);
merge_sort(mid+1, right);

// 3. 子问题合并
// 3.1 按序copy到tmp数组
int i = left;  // 左指针
int j = mid+1; // 右指针
int k = 0;     // tmp数组的指针
while(i <= mid && j <= right)
if(a[i] <= a[j]) tmp[k++] = a[i++];
else tmp[k++] = a[j++];
while(i <= mid) tmp[k++] = a[i++];
while(j <= right) tmp[k++] = a[j++];

// 3.2 tmp数组排好序了，copy回原数组
for (i = left, j = 0; i <= right; i++, j++) a[i] = tmp[j];

}

int main(int argc, char** argv) {
cin >> n;
for(int i = 0; i < n; i++) scanf("%d",a+i);
merge_sort(0,n-1);
for(int i = 0; i < n; i++) printf("%d ",a[i]);
return 0;
}


nnuJacob
28天前
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

bool judge(int x){
int year = x/10000;
int month = x%10000;
month = month / 100;
int day = x %100;
if(month == 0 || month > 12) return false;
if((day == 0 || month != 2 && day > days[month])) return false;
int r = (year%400 == 0 || (year%4 == 0 && year%100 != 0));
if(month == 2 && day > days[2] + r) return false;
return true;
}

int main(int argc, char** argv) {
int date1, date2;
cin >> date1 >> date2;
int res = 0;

for(int i = date1/10000; i < 10000; i++){
// 1. 构造回文，
int date = i; // 回文日期
int tmp = i;
while(tmp){
date = date*10 + tmp%10;
tmp /= 10;
}
// 2. 判断是否在date1和date2之间
if(date < date1 || date > date2)
continue;
// 3. 判断是否是合法日期
if(judge(date))
res++;
}
cout  << res;
return 0;
}


nnuJacob
28天前
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <sstream>
using namespace std;

const int N = 10005;
int n;
int a[N];

int main(int argc, char** argv) {
cin >> n;
int cnt = 0;
string line;
getline(cin, line);
while(n--){
getline(cin, line);
stringstream ssin(line);
while(ssin >> a[cnt])
cnt++;
}
sort(a,a+cnt);
int breaked;
int repeated;
for(int i = 1; i < cnt; i++){
if(a[i] == a[i-1] + 2)
breaked = a[i-1]+1;
if (a[i] == a[i-1])
repeated = a[i];
}
cout << breaked << ' ' << repeated;
return 0;
}