四川省建设监理协会官方网站,建e室内设计网 3d模型医美前台,企业信息管理系统官网,企业管理软件代理D - President (atcoder.jp) #xff08;1#xff09;题目大意 #xff08;2#xff09;解题思路 考虑到z最大不超过1e5#xff0c;N最多不超过100#xff0c;因此可以考虑用背包来写#xff0c;dp[j]表示拿高桥拿j分最少需要花费多少个选民转换#xff0c;最后把答案取…D - President (atcoder.jp) 1题目大意 2解题思路 考虑到z最大不超过1e5N最多不超过100因此可以考虑用背包来写dp[j]表示拿高桥拿j分最少需要花费多少个选民转换最后把答案取个min即可。 3代码实现
#include bits/stdc.h
#define rep(i,z,n) for(int i z;i n; i)
#define per(i,n,z) for(int i n;i z; i--)
#define PII pairint,int
#define fi first
#define se second
#define vi vectorint
#define vl vectorll
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll long long;
const int N 2e5 10;
PII lose[N];
int cnt 0;
ll dp[N];
const ll inf 0x3f3f3f3f3f3f3f3f;
void solve()
{int n;cin n;int win 0,tot 0;for(int i 1;i n;i ) {int x,y,w;cin x y w;tot w;if(x y) win w;else lose[ cnt] {(x y 1) / 2 - x,w};}if(2 * win tot) {cout 0 endl;return;}memset(dp,0x3f,sizeof(dp));dp[0] 0;for(int i 1;i cnt;i ) {for(int j tot;j lose[i].se;j --) {if(dp[j - lose[i].se] ! inf) dp[j] min(dp[j],dp[j - lose[i].se] lose[i].fi);}}int has (tot 1) / 2 - win;ll ok inf;for(int i has;i tot;i ) {ok min(ok,dp[i]);}cout ok endl;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int T 1;// cin T;while(T --) solve();return 0;
}
E - Avoid Eye Contact (atcoder.jp) 1题目大意 2解题思路 考虑预处理出所有障碍物点或者能被看到得点跑一遍bfs即可。 3代码实现
#include bits/stdc.h
#define rep(i,z,n) for(int i z;i n; i)
#define per(i,n,z) for(int i n;i z; i--)
#define PII pairint,int
#define fi first
#define se second
#define vi vectorint
#define vl vectorll
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll long long;
const int N 2e3 10;
int L[N][N],R[N][N],U[N][N],D[N][N];
bool obs[N][N];
int dis[N][N];
string s[N];
const int inf 0x3f3f3f3f;
int mx[4] {1,-1,0,0};
int my[4] {0,0,1,-1};
void solve()
{int n,m;cin n m;for(int i 1;i n;i ) {cin s[i];s[i] s[i];}for(int i 1;i n;i ) {for(int j 1;j m;j ) {if(s[i][j] ) {R[i][j] true;}else if(s[i][j] .) R[i][j] | R[i][j - 1];}for(int j m;j 1;j --) {if(s[i][j] ) {L[i][j] true;}else if(s[i][j] .) L[i][j] | L[i][j 1];}}for(int i 1;i n;i ) {for(int j 1;j m;j ) {if(obs[i][j]) cout i j endl;}}for(int i 1;i m;i ) {for(int j 1;j n;j ) {if(s[j][i] v) {D[j][i] true;}else if(s[j][i] .) D[j][i] | D[j - 1][i];}for(int j n;j 1;j --) {if(s[j][i] ^) {U[j][i] true;}else if(s[j][i] .) U[j][i] | U[j 1][i];}}int sx,sy;int ex,ey;for(int i 1;i n;i ) {for(int j 1;j m;j ) {if(s[i][j] #) obs[i][j] true;obs[i][j] | L[i][j] | R[i][j] | U[i][j] | D[i][j];if(s[i][j] S) sx i,sy j;if(s[i][j] G) ex i,ey j;}}// for(int i 1;i n;i ) {// for(int j 1;j m;j ) {// if(obs[i][j]) cout i j endl;// }// }auto bfs [](int sx,int sy) {queuePII q;q.push({sx,sy});memset(dis,0x3f,sizeof(dis));dis[sx][sy] 0;while(!q.empty()) {auto [x,y] q.front();q.pop();for(int i 0;i 4;i ) {int dx mx[i] x,dy my[i] y;if(dx 0 || dy 0 || dx n || dy m || obs[dx][dy]) continue;if(dis[dx][dy] dis[x][y] 1) {dis[dx][dy] dis[x][y] 1;q.push({dx,dy});}}}};bfs(sx,sy);if(dis[ex][ey] inf) cout -1 endl;else cout dis[ex][ey] endl;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int T 1;// cin T;while(T --) solve();return 0;
}
F - Nim (atcoder.jp) 1题目大意 2解题思路 考虑数字太大我们用数位dp计数状态为dp[pos][i][j][k][r1][r2][r3]表示在二进制位为pos这位时我们第一个数字填i第二个数字填j第三个数字填k并且三个数得余数分别为r1r2r3得方案数有多少。 显然对于非法情况若某一位i^j^k!0则不行因为在异或操作下若这一位异或不为零了那么就永远不可能为0。 对于答案非法情况首先全0得方案需要减去其次是有两个数相同一个数为0得情况也要减去。 3代码实现
#include bits/stdc.h
#define rep(i,z,n) for(int i z;i n; i)
#define per(i,n,z) for(int i n;i z; i--)
#define PII pairint,int
#define fi first
#define se second
#define vi vectorint
#define vl vectorll
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll long long;
const int N 61;
const ll mod 998244353;
ll dp[N][2][2][2][2][2][2][10][10][10];
vectorint nums;
int a,b,c;
ll ksm(ll a,ll b)
{ll rs 1;while(b) {if(b 1) rs rs * a % mod;b 1;a a * a % mod;}return rs;
}
ll calc(int pos,bool z1,bool z2,bool z3,int pi,int pj,int pk,int r1,int r2,int r3)
{if(pos -1) return (!r1 !r2 !r3);if(dp[pos][z1][z2][z3][pi][pj][pk][r1][r2][r3] ! -1) return dp[pos][z1][z2][z3][pi][pj][pk][r1][r2][r3];ll res 0;int up1 z1 ? nums[pos] : 1;int up2 z2 ? nums[pos] : 1;int up3 z3 ? nums[pos] : 1;for(int i 0;i up1;i ) {for(int j 0;j up2;j ) {for(int k 0;k up3;k ) {if(i ^ j ^ k) continue;int nr1 (i 1) ? (r1 (1ll pos)) % a : r1;int nr2 (j 1) ? (r2 (1ll pos)) % b : r2;int nr3 (k 1) ? (r3 (1ll pos)) % c : r3;res calc(pos - 1,z1 i up1,z2 j up2,z3 k up3,i,j,k,nr1,nr2,nr3);res % mod;// cout i j k res endl;}}}return dp[pos][z1][z2][z3][pi][pj][pk][r1][r2][r3] res;
}
void solve()
{ll n;cin n a b c;ll rn n;while(n) {nums.pb(n % 2);n / 2;}memset(dp,-1,sizeof(dp));calc(sz(nums) - 1,true,true,true,0,0,0,0,0,0);ll ans 0;for(int i 0;i 1;i ) {for(int j 0;j 1;j ) {for(int k 0;k 1;k ) {for(int z1 0;z1 1;z1 ) {for(int z2 0;z2 1;z2 ) {for(int z3 0;z3 1;z3 ) {if(dp[sz(nums) - 1][z1][z2][z3][i][j][k][0][0][0] ! -1) ans dp[sz(nums) - 1][z1][z2][z3][i][j][k][0][0][0];ans % mod;}}}} }}n rn;ans - 1;ans - n / lcm(a,b);ans - n / lcm(a,c);ans - n / lcm(b,c);ans (ans % mod mod) % mod;cout ans endl;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int T 1;// cin T;while(T --) solve();return 0;
}
G - Rearranging (atcoder.jp) 1题目大意 2解题思路 我们发现这个题很有可能是全部可以得事实上确实全部可以由Hall定理可知那么考虑怎么构造方案由Hall定理得我们得最大完美匹配在删除一些匹配后依旧成立因此我们只需要一列一列得匹配完即可。 3代码实现
#include bits/stdc.h
#define rep(i,z,n) for(int i z;i n; i)
#define per(i,n,z) for(int i n;i z; i--)
#define PII pairint,int
#define fi first
#define se second
#define vi vectorint
#define vl vectorll
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll long long;
const int N 105;
bool vis[N];
vectorint v[N];
int match[N],Ans[N][N];
bool find(int x)
{vis[x] true;for(auto y : v[x]) {if(!match[y] || (!vis[match[y]] find(match[y]))) {match[y] x;return true;}}return false;
}
void solve()
{int n,m;cin n m;rep(i,1,n) rep(j,1,m) {int x;cin x;v[i].pb(x);}rep(i,1,m) {memset(match,0,sizeof(match));rep(j,1,n) {memset(vis,false,sizeof(vis));if(!find(j)) {cout No \n;return;}}rep(j,1,n) {Ans[match[j]][i] j;v[match[j]].erase(find(v[match[j]].begin(),v[match[j]].end(),j));}}cout Yes \n;rep(i,1,n) {rep(j,1,m) cout Ans[i][j] ;cout \n;}
}
int main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int T 1;// cin T;while(T --) solve();return 0;
}
