JYLeeLYJ

4714

OneSemeserToOneThousand
tulips

starky
zyz529
linjunhao2009
Tkybk_dz
wxcwxc

JYLeeLYJ
10个月前
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

vector<int> c;
int f[5050][5050];
int main() {
int n ; cin >> n ;
for(int i = 0 , last = -1 ; i < n ; ++i) {
int col ; cin >> col ;
if(last != col) {
c.push_back(col);
last = col;
}
}

n = c.size();

for(int len = 2 ; len <= n ; ++ len ){
for(int i = 0 ; i < n ; ++i) {
int j = i + len - 1 ;
if(j >= n) break;
auto & ff = f[i][j] ;
ff = min(f[i+1][j] , f[i][j-1]) + 1;
if(c[i] == c[j]) ff = min(ff , f[i+1][j-1] + 1);
}
}

cout << f[0][n-1] ;
}


JYLeeLYJ
11个月前
#include<iostream>
#include<queue>
#include <cstring>
using namespace std;

char a[1010][1010];
bool vis[1010][1010];
int d[1010][1010];

void bfs(int x , int y , int n , int m){

memset(d, 0x3f ,sizeof d);

auto q = queue<pair<int,int>>{};
q.push({x,y});
int dis = 0 ;
vis[x][y] =true;
while(q.size()){
int cnt = q.size();
while(cnt--){
auto [i , j] = q.front(); q.pop();
d[i][j] = dis;
for(auto & [dx , dy] : {pair{-1 , 0} , {1,0} , {0,1},{0,-1}}){
int u = dx + i , v = j + dy;
if(u >= 0 && u < n && v >= 0 && v < m
&& a[u][v] != 'T' && !vis[u][v]){
q.emplace(u,v);
vis[u][v] = true;
}
}
}
++dis;
}
}

int main(){
int n , m ; cin >> n >> m;
int ex , ey ;
int sx , sy ;
for(int i = 0 ; i < n ; ++i) {
cin >> a[i];
for(int j = 0 ; j < m ; ++j){
if(a[i][j] == 'S') sx = i , sy = j;
else if(a[i][j] == 'E') ex = i , ey = j;
}
}

bfs(ex , ey , n , m);
int ans = 0 ;
int dis = d[sx][sy];
for(int i = 0 ; i < n ; ++i) {
for(int j = 0 ; j < m ; ++j){
if(a[i][j] > '0' && a[i][j] <= '9' && d[i][j] <= dis)
ans += a[i][j] - '0';
}
}

cout << ans ;
}


JYLeeLYJ
11个月前

#include<iostream>

using namespace std;

int primes[] = {0,2,3,5,7,11,13,17,19,23};
int st[10] = {30};
int n;

void dfs(int u , long long v , int cur_g ,  long long & ans , int & g ){
if(v > n || v <= 0 || cur_g > 2000) return ;
if(u == 10){
if(cur_g > g) ans = v , g = cur_g;
else if(cur_g == g) ans = min(ans , v) ;
return ;
}

int c = 0 ;
for(; c < st[u-1] && v <= n; ++c) v *= primes[u];
st[u] = c;
for(int i = 0 ; i <= c ; ++i) {
dfs(u + 1 , v , cur_g * (st[u] + 1) , ans , g);
--st[u];
v /= primes[u];
}
st[u] = 0;
}

int main(){
cin >> n;
long long ans = 0;
int g = 0;
int cur_g = 1;
dfs(1 , 1 , cur_g , ans , g);
cout << ans ;
}


JYLeeLYJ
11个月前
#include <iostream>

using namespace std;

int main(){
int t; cin >> t;
while(t--){
int n ; cin >> n ;
int a[110];
for(int i = 0 ; i < n ; ++i) cin >> a[i];
int i = 0 ;
int ans = 0 ;
while(i < n && a[i] == 0) ++ans , ++i;
int zcnt = 0;
for(;i < n ; ++i) {
if(a[i] == 1 ) {
if(zcnt > 1) ans += zcnt;
zcnt= 0 ;
}
else ++zcnt;
}
ans += zcnt;
cout << n - ans << endl;
}
}


JYLeeLYJ
11个月前

#include <iostream>
#include <vector>
#include <cassert>
#include <numeric>
#include <map>
#include <set>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
constexpr int N = 4e4 + 10;

vector<int> primes{};
map<int,int> prime_cnts[4];
set<int> prime_set;
bool test[N];

void init(){
primes.reserve(N / 5);
for(long long i = 2; i < N ; ++i) {
if(test[i]) continue ;
primes.push_back(i);
for(auto j = i * i ; j < N ; j += i ) test[j] = true;
}
}

void factoring(int n , int j){
for(int i : primes){
if(i * i > n) break;
int c = 0;
while(n % i == 0) n /= i , ++c;
if(c) prime_cnts[j][i] = c , prime_set.insert(i);
}
if(n > 1) {
prime_set.insert(n);
prime_cnts[j][n] = 1;
}
}

void reset(){
for(auto & ps : prime_cnts) ps.clear();
prime_set.clear();
}

int main(){
int n ; cin >> n;
init();
while(n--){
int a1 , a0 , b1 , b0 ; cin >> a0 >> a1 >> b0 >> b1;

reset();

factoring(a0 , 0);
factoring(a1 , 1);
factoring(b0 , 2);
factoring(b1 , 3);

auto get_count_in_p = [](int ca0 , int ca1 , int cb0 , int cb1){

int left = 0 , right = numeric_limits<int>::max() - 1;
// assert(ca0 >= ca1);
if(ca0 == ca1) left = max(left , ca1);
else left = max(left , ca1) , right= min(right , ca1);

// assert(cb0 <= cb1) ;
if(cb0 == cb1) right = min(right , cb1);
else left = max(left , cb1) , right = min(right , cb1);

return max(0 , right - left + 1);
};

int ans = 1;

for(int p : prime_set){
if(ans == 0) break;

int ca0 = prime_cnts[0][p];
int ca1 = prime_cnts[1][p];
int cb0 = prime_cnts[2][p];
int cb1 = prime_cnts[3][p];

ans *= get_count_in_p(ca0 , ca1 , cb0 , cb1);
}

cout << ans << endl;
}
}


JYLeeLYJ
11个月前

#include <iostream>
#include <vector>

using namespace std;
constexpr int N = 1e6 + 10 ;
constexpr int mod = 1e9 + 7;
vector<int> primes{};
bool test[N];
int cnts[N];

void init_primes(){
primes.reserve(N / 5);
for(long long i = 2 ; i < N ; ++i){
if(test[i]) continue ;
primes.push_back(i);
for(auto j = i * i ; j < N ; j +=i ) test[j] = true;
}
}

void count(int n){
for(int i = 0 ; i < primes.size() ; ++i) {
int p = primes[i];
for(long long j = p ; j <= n; j *= p ){
cnts[i] += (n / j ) * 2;
}
}
}

int main(){
int n ; cin >> n ;
init_primes();
count(n);
long long ans = 1 ;
for(int i = 0 ; i < primes.size() ;++i) {
ans = (ans * (cnts[i] + 1)) % mod;
}
cout << ans ;
}


JYLeeLYJ
11个月前
#include <iostream>
#include <cstring>
using namespace std;
constexpr int N = 1e6 + 10;

int a[N / 5];
bool vis[N];
int cnt[N];
int ans[N];

int main(){
int n ; cin >> n ;
int maxv = 0;
for(int i = 0 ; i < n ; ++i) cin >> a[i] , cnt[a[i]] ++ , maxv = max(maxv , a[i]);

for(int i = 0 ; i < n ; ++i) {
if(vis[a[i]]) continue ;
for(int j = a[i] ; j <= maxv; j += a[i]){
ans[j] += cnt[a[i]];
}
vis[a[i]] = true;
}

for(int i = 0; i < n ; ++i) cout << ans[a[i]] - 1<< "\n";

}


JYLeeLYJ
11个月前
#include <iostream>
#include <vector>
#include <cstring>
#include <cassert>

using namespace std;

constexpr int N = 1e6 + 10;

vector<int> primes{};
vector<int> p2{};
bool test[N];

void init_primes(){
primes.reserve(20000);
for(long long i = 2 ; i < 50000 ; ++i ) {
if(test[i]) continue ;
primes.push_back(i);
for(long long j = i * i ; j < 50000; j += i)
test[j] = true;
}
}

int main(){

init_primes();
long long l , r ;
while(cin >> l >> r){
memset(test, 0 , sizeof test);

for(int i : primes){
if(i > r) break;

long long beg = (l / i) * i;
if(beg < l) beg += i;
if(beg == i) beg += i;

for(long long j = beg ; j <= r ; j += i) {
test[j - l] = true;
}
}

int minv = N , maxv = 0 ;
int mil , mir , mal , mar;
if( l == 1) test[0] = true;
for(int i = 0 , prev = -1; i <= r - l ; ++i){
if(test[i]) continue ;
if(prev >= 0) {
if(i - prev < minv) mil = prev , mir = i , minv = i - prev;
if(i - prev > maxv) mal = prev , mar = i , maxv = i - prev;
}
prev = i;
}

if(maxv)
cout << mil + l << "," << mir + l << " are closest, "
<< mal + l<<"," << mar + l << " are most distant." << endl;
else
cout << "There are no adjacent primes." << endl;
}

}


JYLeeLYJ
11个月前
#include <iostream>
#include <vector>
using namespace std;
constexpr int N = 1e6 + 10;

bool test[N];

int main(){
int n ; cin >> n ;
auto primes = vector<int>{} ; primes.reserve(n);

for(long long i = 2 ; i <= n ; ++i) {
if(test[i]) continue ;
primes.push_back(i);
for(long long j = i * i ; j <= n ; j += i) {
test[j] = true;
}
}
for(int i: primes) {
int cnt = 0 ;
for(long long j = i ; j <= n  ; j *= i){
cnt += n / j ;
}
if(cnt) cout << i << " " << cnt << endl;
}

}


JYLeeLYJ
11个月前
#include <iostream>

using namespace std;

constexpr long long mod = 100003  ;

long long fpow (long long n , long long e){
long long ans = 1;
while(e){
if(e & 1) ans *= n ;
n *= n ;
ans %= mod;
n %= mod;
e >>= 1;
}
return ans;
}

int main(){
long long m , n ; cin >> m >> n ;
if(m == 1) {
cout << 1 << endl;
return 0;
}

m %= mod ;
auto ans = m * ((fpow(m , n - 1) + mod - fpow(m -1, n - 1))%mod);
ans %= mod;
cout << ans << endl;
}