fwyize

1286

Verney_the_Bear
DreamDimo
ckcyi

incra

leaver
wanghai673
Enjoycode

AvariceZhao

fwyize
1天前

### 单调栈二分思路

#### C++ 代码

# include<iostream>
# include<cstring>
# include<algorithm>

using namespace std;
const int N = 100010;
int w[N];
int stk[N],top;
int ans[N];
int n;

int main(){
cin >> n;
for(int i=0;i<n;++i){
cin >> w[i];
}

for(int i=n-1;i>=0;--i){
if(!top || w[i] <= w[stk[top]]){
ans[i] = -1;
}else{
// 单调栈二分 找到第一个比w[i]小的元素对应下标
int l = 1,r = top;
while(l < r){
int mid = (l + r) >> 1;
if(w[stk[mid]] < w[i]) r = mid;
else l = mid + 1;
}
ans[i] = stk[l] - i - 1;
}
// 更新单调栈  等于时不需要更新 维护严格单调递减
if(!top || w[i] < w[stk[top]]){
stk[++top] = i;
}
}

for(int i=0;i<n;++i) cout << ans[i] << " ";
cout << endl;
return 0;
}


# include<iostream>
# include<cstring>
# include<algorithm>
# include<map>

using namespace std;
const int N = 100010;
int w[N];
int stk[N],top;
map<int,int> mp;
int ans[N];
int n;

int main(){
cin >> n;
for(int i=0;i<n;++i){
cin >> w[i];
}

// 维护一个单调递增的map (负数,索引)
for(int i=n-1;i>=0;--i){
// 二分查找 第一个比当前值大的元素
auto it = mp.upper_bound(-w[i]);
if(it == mp.end()) ans[i] = -1;
else ans[i] = it->second - i - 1;
if(mp.empty() || -(mp.rbegin()->first) > w[i]){
mp.insert({-w[i],i});
}
}

for(int i=0;i<n;++i) cout << ans[i] << " ";
cout << endl;
return 0;
}


fwyize
1天前

### 线性筛预处理+容斥原理计数

# include<iostream>
# include<cstring>
# include<algorithm>

using namespace std;
const int N = 1000010;
bool st[N];
int primes[N],cnt;
int n;

void init(int n){
for(int i=2;i<=n;++i){
if(!st[i]) primes[cnt++] = i;
for(int j=0;primes[j]<=n/i;++j){
st[primes[j]*i] = true;
if(i % primes[j] == 0) break;
}
}
}

int main(){
cin >> n;
// 1.一步一步分解1 * 2 * 3 * ... * n
// 2.可以考虑预处理质因数 用筛法的思想进行计数
// 3.例如 针对质数2   2的倍数都包含质因子2  同时2的平方的倍数都包含两个质因子2
init(n);

for(int i=0;i<cnt;++i){
int p = primes[i];
int num = 0;
int t = n;
while(t){
num += t / p;
t /= p;
}
if(num) cout << primes[i] << " " << num << endl;
}
return 0;
}


fwyize
1天前

### 优化枚举+区间筛思想

# include<iostream>
# include<cstring>
# include<algorithm>
# include<cmath>

using namespace std;
typedef long long ll;
const int N = 50010,M = 1000010;
bool st[N];
int primes[N],cnt;

int l,r;
bool vis[M];
ll nums[M];
int idx;

void init(int n){
for(int i=2;i<=n;++i){
if(!st[i]) primes[cnt++] = i;
for(int j=0;primes[j]<=n/i;++j){
st[primes[j]*i] = true;
if(i % primes[j] == 0) break;  // 此时的primes[j]一定是i的最小质数  分类讨论证明即可
}
}
}

// 由于值域很大 并且区间大小满足条件  使用区间筛的思想
// 区间筛 先预处理出sqrt(U)的所有质数 使用埃式筛法 筛掉区间内的合数即可
int main(){
init(50000);

// l和r对于primes[i]来说
while(cin >> l >> r){
memset(vis,false,sizeof vis);
idx = 0;

for(int i=0;i<cnt;++i){
ll p = primes[i];
// 一开始这里nyx了 (l + p - 1) / p * p写成了p*(l+p-1)/p
for (ll j = max(p * 2, (l + p - 1) / p * p); j <= r; j += p)
vis[j - l] = true;
}

for(int i=0;i<=r-l;++i){
if(!vis[i] && i + l >= 2) nums[idx++] = 1ll * i + l;
}
if(idx < 2){
continue;
}
int maxv = 0,minv = 0;
for(int i=0;i<idx-1;++i){
if(nums[i+1] - nums[i] > nums[maxv+1] - nums[maxv]){
maxv = i;
}
if(nums[i+1] - nums[i] < nums[minv+1] - nums[minv]){
minv = i;
}
}
printf("%lld,%lld are closest, %lld,%lld are most distant.\n",nums[minv],nums[minv+1],nums[maxv],nums[maxv+1]);
}
return 0;
}


fwyize
4天前

### 找规律+线性筛法

# include<iostream>
# include<cstring>
# include<algorithm>

using namespace std;
const int N = 100010;
bool st[N];
int primes[N],cnt;
int n;

int main(){
cin >> n;
// 2~n+1范围的数  本身是质数 质数的倍数累加k
if(n <= 2){
cout << "1" << endl;
for(int i=1;i<=n;++i) cout << "1" << " ";
cout << endl;
}else{
cout << "2" << endl;
n ++;
for(int i=2;i<=n;++i){
if(!st[i]){
primes[cnt++] = i;
cout << "2" << " ";
}else{
cout << "1" << " ";
}
for(int j=0;primes[j]<=n/i;++j){
st[primes[j]*i] = true;
if(i % primes[j] == 0) break;  // 此时的primes[j]一定是i的最小质数  分类讨论证明即可
}
}
cout << endl;
}
return 0;
}


fwyize
4天前

### 裸的线性筛+枚举

# include<iostream>
# include<cstring>
# include<algorithm>

using namespace std;
int n;
const int N = 1000010;
bool st[N];
int primes[N],cnt;

void get_prime(int n){
for(int i=2;i<=n;++i){
if(!st[i]) primes[cnt++] = i;
for(int j=0;primes[j]<=n/i;++j){
st[primes[j]*i] = true;
if(i % primes[j] == 0) break;  // 此时的primes[j]一定是i的最小质数  分类讨论证明即可
}
}
}

int main(){
get_prime(1e6);
while(cin >> n,n){
for(int i=1;i<cnt;++i){
int a = primes[i];
int b = n - a;
if(!st[b]){
printf("%d = %d + %d\n",n,a,b);
break;
}
}
}
return 0;
}


fwyize
4天前

### 思路

#### C++ 代码

# include<iostream>
# include<algorithm>
# include<cstring>
typedef long long ll;

using namespace std;
const int N = 110;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int a[N],b[N]; // a存储数字  b存储运算符其中1表示加法 2表示乘法
ll f[N][N][2]; // 维护区间的最大值和最小值
int n;

int main(){
cin >> n;
// 预处理输入
char ops[2];
for(int i=1;i<=n<<1;++i){
if(i & 1){
cin >> ops;
if(ops[0] == 't'){
b[i / 2] = 1;
b[i / 2 + n] = 1;
}else{
b[i / 2] = 2;
b[i / 2 + n] = 2;
}
}else{
cin >> a[i / 2];
a[i / 2 + n] = a[i / 2];
}
}

// 这里需要分别赋初值  因为可能存在负数
for(int i=1;i<=2*n;++i){
for(int j=1;j<=2*n;++j){
f[i][j][0] = -INF;
f[i][j][1] = INF;
}
}
// 赋初值
for(int i=1;i<=2*n;++i){
f[i][i][0] = f[i][i][1] = a[i];
}

// 区间dp递推
for(int len=2;len<=n;++len){
for(int i=1;i<=2*n-len+1;++i){
int j = i + len - 1;
for(int k=i;k<j;++k){
// 加法操作负数不影响最大最小值判定
if(b[k] == 1){
f[i][j][0] = max(f[i][j][0],f[i][k][0]+f[k+1][j][0]);
f[i][j][1] = min(f[i][j][1],f[i][k][1]+f[k+1][j][1]);
}else{
// 乘法运算的最大值可能是两个最大正数的乘积或者两个最小负数的乘积
// 最小值可能是最大正数*最小负数的乘积/最小正数的乘积
f[i][j][0] = max(f[i][j][0],max(f[i][k][0]*f[k+1][j][0],f[i][k][1]*f[k+1][j][1]));
f[i][j][1] = min(f[i][j][1],min({f[i][k][0]*f[k+1][j][1],f[i][k][1]*f[k+1][j][1],f[i][k][1]*f[k+1][j][0]}));
}
}
}
}

ll res = -INF;
vector<int> ans;
for(int i=1;i<=n;++i){
if(f[i][i+n-1][0] > res){
res = f[i][i+n-1][0];
ans.clear();
ans.push_back(i);
}else if(f[i][i+n-1][0] == res){
ans.push_back(i);
}
}

cout << res << endl;
for(auto& v:ans) cout << v << " ";
cout << endl;
return 0;
}



fwyize
7天前

### 无向图欧拉路径+并查集判断连通性

# include<iostream>
# include<cstring>
# include<algorithm>

using namespace std;
const int N = 100010;
int t;
int indeg[N],outdeg[N],p[N];
bool st[N];
int n;

int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}

void init(){
memset(indeg,0,sizeof indeg);
memset(outdeg,0,sizeof outdeg);
memset(st,false,sizeof st);
for(int i=0;i<26;++i) p[i] = i;
}

int main(){
cin >> t;

char str[1010];
while(t--){
init();
cin >> n;
for(int i=0;i<n;++i){
cin >> str;
int len = strlen(str);
int a = str[0] - 'a', b = str[len - 1] - 'a';
st[a] = st[b] = true;
outdeg[a] ++, indeg[b] ++ ;
p[find(a)] = find(b);
}

// 判断入度和出度关系
int start = 0,end = 0;
bool ok = true;
for(int i=0;i<26;++i){
if(indeg[i] == outdeg[i] + 1){
end ++;
}else if(outdeg[i] == indeg[i] + 1){
start ++;
}else if(indeg[i] != outdeg[i]){
ok = false;
break;
}
}
if(!ok || !(!start && !end || start == 1 && end == 1)){
printf("The door cannot be opened.\n");
continue;
}
// 判断图连通性
int t = -1;
for(int i=0;i<26;++i){
if(st[i]){
if(t == -1){
t = find(i);
}else{
if(t != find(i)){
ok = false;
break;
}
}
}
}

if(!ok) printf("The door cannot be opened.\n");
else{
printf("Ordering is possible.\n");
}
}

return 0;
}


fwyize
7天前

### 欧拉回路

# include<cstring>
# include<algorithm>
# include<iostream>

using namespace std;
const int N = 100010,M = 400010;
int h[N],e[M],ne[M],idx;
bool used[M];         // 标记边是否被使用
int ans[M / 2],cnt;   // 存储逆序欧拉回路
int n,m;
int type;
int indeg[N],outdeg[N];

e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}

void dfs(int u){
// 这里加引用使得删除的边应用于全局
for(int &i=h[u];i!=-1;){
if(used[i]){
i = ne[i];
continue;
}
used[i] = true;
// 无向图 将编号i的边和编号i^1的边都置为访问过
if(type == 1) used[i ^ 1] = true;

int t;

if(type == 1)
{
t = i / 2 + 1;        // 边的编号下标从1开始
if (i & 1) t = -t;    // 如果i是偶数说明应该输出正数 否则是对称边输出负数
}
else t = i + 1;

int j = e[i];
i = ne[i];
dfs(j);
ans[++cnt] = t;
}
}

int main(){
cin >> type;
cin >> n >> m;
memset(h, -1, sizeof h);

for(int i=0;i<m;++i){
int a,b;cin >> a >> b;
indeg[b] ++,outdeg[a] ++;
}

if(type == 1){
for(int i = 1;i <= n;i ++){
if((indeg[i] + outdeg[i]) & 1){
printf("NO\n");
return 0;
}
}
}else{
for(int i = 1;i <= n;i ++){
if(indeg[i] != outdeg[i]){
printf("NO\n");
return 0;
}
}
}

// 从某一个起点开始
for(int i=1;i<=n;++i){
if(h[i] != -1){
dfs(i);
break;
}
}

if(cnt < m){
printf("NO\n");
return 0;
}

cout << "YES" << endl;
for(int i=cnt;i;i --) printf("%d ", ans[i]);
cout << endl;
return 0;
}



fwyize
7天前

### 邻接矩阵+欧拉回路+字典序最小路径

# include<iostream>
# include<cstring>
# include<algorithm>

using namespace std;
const int N = 510;
int n = 500,m;
int g[N][N];
int ans[1100],cnt;
int deg[N];

void dfs(int u){
for(int i=1;i<=n;++i){
if(g[u][i]){
g[u][i] --,g[i][u] --;
dfs(i);
}
}
ans[++cnt] = u;
}

int main(){
int m;
cin >> m;
for(int i=0;i<m;++i){
int a,b;
cin >> a >> b;
g[a][b] ++,g[b][a] ++;
deg[a] ++,deg[b] ++;
}
int start = 1;
while(!deg[start]) start ++;
for(int i=1;i<=n;++i){
if(deg[i] & 1){
start = i;
break;
}
}

dfs(start);

// 输出欧拉路径
for(int i=cnt;i>=1;--i) cout << ans[i] << endl;
return 0;
}


fwyize
7天前

### 欧拉回路问题

# include<iostream>
# include<cstring>
# include<algorithm>
# include<cmath>

using namespace std;

int main(){
double x1,y1,x2,y2;
cin >> x1 >> y1;

double sum = 0.0;
while(cin >> x1 >> y1 >> x2 >> y2){
double x = x1 - x2;
double y = y1 - y2;
sum += sqrt(x * x + y * y) * 2;    // 无向边视为两条有向边
}

int minutes = round(sum / 1000 / 20 * 60);  // 四舍五入计算分钟数
int hours = minutes / 60;
minutes %= 60;

printf("%d:%02d\n",hours,minutes);
return 0;
}