2248

T-D-S

RyanMoriarty
LvTao
SinceJuly
yxc

limie
tgeuuy
__Meilyゝ海绵宝宝亮亮鞋
MZZDX

karrrrri

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

using namespace std;

int main()
{
int a,b;
cin >> a >> b;

string c = to_string(a + b);

reverse(c.begin(),c.end());

string ans;
for(int i = 0;i < c.size();i ++)
{
ans += c[i];

if(i % 3 == 2 && isdigit(c[i + 1]))
ans += ',';
}

reverse(ans.begin(),ans.end());

cout << ans;

return 0;
}


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

using namespace std;

const int N = 60;
const int M = 60;
const int INF = 0x3f3f3f3f;

int n,m;
char g[N][M];
int dx[4] = {0,0,-1,1},dy[4] = {-1,1,0,0};

struct node
{
int x,y;
};

vector<node> s[2];

void dfs(int x,int y,vector<node>& s)
{
s.push_back({x,y});
g[x][y] = '.';
for(int i = 0;i < 4;i ++)
{
int nx = x + dx[i],ny = y + dy[i];
if(nx >= 1 && nx <= n && ny >= 1 && ny <= m && g[nx][ny] == 'X')
dfs(nx,ny,s);
}
}

int main()
{
cin >> n >> m;

for(int i = 1;i <= n;i ++)
scanf("%s",g[i] + 1);

for(int i = 1,k = 0;i <= n;i ++)
for(int j = 1;j <= m;j ++)
if(g[i][j] == 'X')
dfs(i,j,s[k ++]);

int ans = INF;
for(auto a : s[0])
for(auto b : s[1])
ans = min(ans,abs(a.x - b.x) + abs(a.y - b.y));

cout << ans - 1;

return 0;
}


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

using namespace std;

const int N = 1e6 + 10;

int a[N];

{
a[l] ++;
a[r + 1] --;
}

int main()
{
int n,k;
cin >> n >> k;

while(k --)
{
int l,r;
cin >> l >> r;

}

for(int i = 1;i <= n;i ++)
a[i] += a[i - 1];

sort(a + 1,a + n + 1);

cout << a[n + 1 >> 1];

return 0;
}


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <set>

using namespace std;

int getnum(string s,int k)
{
int res = 0;
for(auto c : s)
res = res * k + c - '0';

return res;
}

int main()
{
string a,b;
cin >> a >> b;

set<int> s;
for(auto& c : a)
{
c = (c == '0' ? '1' : '0');
s.insert(getnum(a,2));
c = (c == '0' ? '1' : '0');
}

for(auto& c : b)
{
char t = c;
for(int i = 0;i < 3;i ++)
if(i + '0' != t)
{
c = i + '0';
int x = getnum(b,3);
if(s.count(x))
{
cout << x;
return 0;
}
}

c = t;
}

return 0;
}


f[i][j] = f[i - 1][j] | f[i - 1][j - w[i]] | f[i - 1][j + w[i]]

Δ：这个题中，假设我们所有的砝码总质量为m，那么实际上可以凑出的重量范围应该是[-m,m]

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

using namespace std;

const int N = 110;
const int M = 2e5 + 10;
const int dm = 1e5;

int w[N];
bool f[N][M];

int main()
{
int n,m = 0;
cin >> n;

for(int i = 1;i <= n;i ++)
cin >> w[i],m += w[i];

f[0][dm] = true;
for(int i = 1;i <= n;i ++)
for(int j = -m;j <= m;j ++)
{
f[i][j + dm] = f[i - 1][j + dm];

if(j - w[i] >= -m)
f[i][j + dm] |= f[i - 1][j - w[i] + dm];
if(j + w[i] <= m)
f[i][j + dm] |= f[i - 1][j + w[i] + dm];
}

int ans = 0;
for(int j = 1;j <= m;j ++)
if(f[n][j + dm])
ans ++;

cout << ans;

return 0;
}


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

using namespace std;

typedef long long ll;

int main()
{
ll n;
cin >> n;

printf("%02lld:%02lld:%02lld",n / 1000 / 60 / 60 % 24,n / 1000 / 60 % 60,n / 1000 % 60);

return 0;
}


01背包没有其它写法，最终还是只能这样写，只能选择更换体积和价值的位置

• 原f[i][j]表示：从前i件物品里选，总体积不超过j时所能获得的最大价值
• 现f[i][j]表示：从前i件物品里选，总价值不超过j时所需要的最小背包体积

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

using namespace std;

const int N = 1e3 + 10;
const int M = 3e4 + 10;

int v[N],w[N],f[M];

int main()
{
int n,m;
cin >> n >> m;

for(int i = 1;i <= n;i ++)
cin >> v[i];

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

sum += w[i];
}

memset(f,0x3f,sizeof(f));
f[0] = 0;

for(int i = 1;i <= n;i ++)
for(int j = sum;j >= w[i];j --)
f[j] = min(f[j],f[j - w[i]] + v[i]);

for(int i = sum;i >= 0;i --)
if(f[i] <= m)
{
cout << i;
return 0;
}
}


（1）找一个起点，从这个点出发，到离它最远的点的距离最小：
（2）有多次询问，每次询问一个点，要求输出从起点到这个点距离最小且价值最大的路径。

（1）先用Floyd计算多源最短路，再枚举起点，暴力算出每种情况下的最远距离，取最小值；
（2）Dijkstra算法，按照距离优先，价值其次的原则进行更新。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <stack>

using namespace std;

const int N = 1010;
const int INF = 0x3f3f3f3f;

struct node
{
int a,b;
}dis[N],g[N][N];

int n,m;
int path[N];
bool vis[N];

void dijkstra(int s)
{
for(int i = 1;i <= n;i ++)
dis[i].a = INF;
dis[s].a = 0;

for(int i = 1;i <= n;i ++)
{
int k,mind = INF;
for(int j = 1;j <= n;j ++)
if(!vis[j] && dis[j].a < mind)
k = j,mind = dis[j].a;

vis[k] = true;

for(int j = 1;j <= n;j ++)
if(dis[k].a + g[k][j].a < dis[j].a || dis[k].a + g[k][j].a == dis[j].a && dis[k].b + g[k][j].b > dis[j].b)
dis[j] = {dis[k].a + g[k][j].a,dis[k].b + g[k][j].b},path[j] = k;
}
}

int main()
{
cin >> n >> m;

for(int i = 1;i <= n;i ++)
for(int j = 1;j <= n;j ++)
if(i != j)
g[i][j].a = INF;

while(m --)
{
int x,y,a,b;
scanf("%d %d %d %d",&x,&y,&a,&b);

g[x][y] = g[y][x] = {a,b};
}

for(int k = 1;k <= n;k ++)
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= n;j ++)
if(g[i][k].a + g[k][j].a < g[i][j].a)
g[i][j] = {g[i][k].a + g[k][j].a,0};

int s,mind = INF;
for(int i = 1;i <= n;i ++)
{
int maxd = 0;
for(int j = 1;j <= n;j ++)
maxd = max(maxd,g[i][j].a);

if(maxd < mind)
s = i,mind = maxd;
}

dijkstra(s);

cout << s << endl;

int k;
cin >> k;

while(k --)
{
int e;
cin >> e;

int end = e;
stack<int> ans;
while(end != s)
{
ans.push(end);
end = path[end];
}

cout << s;
while(ans.size())
{
printf("->%d",ans.top());
ans.pop();
}
cout << endl << dis[e].a << ' ' << dis[e].b << endl;
}

return 0;
}