oyel

875

oyel
7个月前
# include <iostream>

using namespace std;

void divide(int x){
if (x <= 2){
cout << x << " " << 1 << endl;
return;
}
for (int i=2; i <= x / i; i++){
// n中最多只包含一个大于sqrt(n)的因子
if (x % i == 0){
// i一定是质数(2到i-1的因子都已除干净)
int s = 0;
while(x % i == 0){
x /= i;
s++;
}
cout << i << " " << s << endl;
}
}
if (x > 1) cout << x << " " << 1 << endl;
cout << endl;
return;
}

int main(){
int n;
cin >> n;
while(n--){
int x;
cin >>x;
divide(x);
}
return 0;
}


oyel
7个月前
# include <iostream>
# include <cstring>

using namespace std;

const int N = 510;
int g[N][N];
int dist[N];
bool st[N];

int main(){
int n, m;
cin >> n >> m;
memset(g, 0x3f, sizeof g);
while(m--){
int x, y, z;
cin >> x>> y >> z;
g[x][y] = g[y][x] = min(g[x][y], z);
}

int res = 0;
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;  // 1号元素
for (int i=0; i<n; i++){
int t = -1;
for (int j = 1; j <= n; j++){
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
}

if (dist[t] == 0x3f3f3f3f){
res = 0x3f3f3f3f;
break;
}
st[t] = true;
res += dist[t];
for (int j=1; j<=n; j++){
if (!st[j])
dist[j] = min(dist[j], g[t][j]);
}
}
if (res == 0x3f3f3f3f) cout << "impossible" << endl;
else cout << res << endl;
return 0;
}



oyel
7个月前
1. 维护一个单调减小的栈，若当前柱子高于栈顶的柱子，退栈直到符合单调性；否则加入栈顶。
2. 每次退栈时，累加雨水的体积（每次算一层）。
3. 最后栈是一个单调栈，结束程序即可
# include <iostream>
# include <stack>

using namespace std;

const int N = 100010;
int a[N];

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

stack<int> st;
for (int i=0; i<n; i++){
while(!st.empty() && a[st.top()] < a[i]){
int t = st.top();
st.pop();
if (!st.empty()){
int l = i - st.top() - 1;
int h = min(a[i], a[st.top()]) - a[t];
res += l * h;
}
}
st.push(i);
}
cout << res << endl;
return 0;
}


oyel
7个月前

01背包2维dp，思路比较清晰。
res数组存方案数，注意base case为1。

# include <iostream>

using namespace std;

const int N = 1010, V = 1010, MOD = 1e9 + 7;
int dp[N][V], res[N][V];
int v[N], w[N];

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

for (int j=0; j <= vol; j++) res[0][j] = 1;
for (int i=0; i <= n; i++) res[i][0] = 1;

for(int i=1; i<=n; i++){
for (int j=1; j <=vol; j++){
int maxv = dp[i-1][j];
int t = res[i-1][j];
if (j - v[i-1] >= 0){
if (maxv == dp[i-1][j-v[i-1]] + w[i-1]){
t = (t + res[i-1][j-v[i-1]]) % MOD;
}else if (maxv < dp[i-1][j-v[i-1]] + w[i-1]){
t = res[i-1][j-v[i-1]];
maxv = dp[i-1][j-v[i-1]] + w[i-1];
}
}
res[i][j] = t;
dp[i][j] = maxv;
}
}

cout << res[n][vol] << endl;
return 0;

}


oyel
11个月前

#### C++ 代码

#include <iostream>
#include <queue>

using namespace std;

const int N = 1010;

int g[N][N], v[N][N], n;
queue<pair<int, int> > q;
pair<int, int> mem[N][N];

void bfs(){
int dx[4] = {0, 0, 1, -1}, dy[4] = {-1, 1, 0, 0};
q.push({n-1, n-1});
v[n-1][n-1] = 1;
while(!q.empty()){
auto t = q.front();
q.pop();
if(t.first == 0 && t.second == 0) return;
for(int i=0; i<4; i++){
int x = t.first + dx[i], y = t.second + dy[i];
if(x>=0 && x < n && y>=0 && y < n && g[x][y] == 0 && v[x][y] == 0){
q.push({x, y});
v[x][y] = 1;
mem[x][y] = {t.first, t.second};
}
}
}
return;
}

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

bfs();

int x = 0, y = 0;
while(x < n -1 || y < n - 1){
cout << x << " " << y << endl;
int tx = x, ty = y;
x = mem[tx][ty].first;
y = mem[tx][ty].second;
}
cout << x << " " << y << endl;
}


oyel
11个月前
##### 按行搜索
#include <iostream>

using namespace std;

const int N = 20;
int n;
char mat[N][N];
int col[N], dg1[N], dg2[N];

void dfs(int x){
if(x == n){
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
cout << mat[i][j];
}
cout << endl;
}
cout << endl;
return;
}

for(int i=0; i<n; i++){
if(col[i] || dg1[i-x+n] || dg2[i+x]) continue;
col[i] = 1;
dg1[i - x + n] = 1;
dg2[i + x] = 1;
mat[x][i] = 'Q';
dfs(x+1);
col[i] = 0;
dg1[i-x+n] = 0;
dg2[i+x] = 0;
mat[x][i] = '.';
}
}

int main(){
cin >> n;

for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
mat[i][j] = '.';

dfs(0);
return 0;

}


#### 每一个格子搜索

#include <iostream>

using namespace std;

const int N = 20;
int n;
char mat[N][N];
//int col[N], dg1[N], dg2[N];
int row[N], col[N], dg1[N], dg2[N];

void dfs(int x, int s_i, int s_j){
if(s_i >= n){
if(x == n){
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
cout << mat[i][j];
}
cout << endl;
}
cout << endl;
}
return;
}

dfs(x, s_i+(s_j+1)/n, (s_j+1)%n);
if(!row[s_i] && !col[s_j] && !dg1[s_j-s_i+n] && !dg2[s_j+s_i]){
row[s_i] = col[s_j] = dg1[s_j-s_i+n] = dg2[s_j+s_i] = 1;
mat[s_i][s_j] = 'Q';
dfs(x+1, s_i+(s_j+1)/n, (s_j+1)%n);
row[s_i] = col[s_j] = dg1[s_j-s_i+n] = dg2[s_j+s_i] = 0;
mat[s_i][s_j] = '.';
}
return;

}

int main(){
cin >> n;

for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
mat[i][j] = '.';

dfs(0, 0, 0);
return 0;

}