SDNU_ACM_ICPC_2019_Winter_Practice_8th（柳雨欣的十宗罪）解析~~
A - 柳予欣的暴食
状压dp入门
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int mod = 100000000;
#define ll long long int
int mp[15];
int dp[15][1 << 15];
int n, m;
void init() {
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
int ans = 0;
for (int j = 0; j < m; j++) {
int t; scanf("%d", &t);
ans = (ans << 1) + t;
}
mp[i] = ans;
}
}
bool judge(int a,int b) {
if ((b&mp[a])!=b)return 0;
if (b&(b << 1))return 0;
return 1;
}
int main() {
while (~scanf("%d%d", &n, &m)) {
init();
for (int i = 1; i <= n; i++) {
for (int j = 0; j < (1 << m); j++) {
if (!judge(i, j))continue;
for (int k = 0; k < (1 << m); k++) {
if (j&k)continue;
dp[i][j] += dp[i - 1][k];
dp[i][j] %= mod;
}
}
}
int ans = 0;
for (int i = 0; i < (1 << m); i++) {
ans += dp[n][i];
ans %= mod;
}
cout << ans << '\n';int k;
}
} B - 柳予欣的贪婪
完全背包
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f3f
int sum[10005];
int v[10005];
int w[10005];
int main()
{
int te;
cin >> te;
while (te--)
{
memset(sum, inf, sizeof(sum));
int a, b;
scanf("%d%d", &a, &b);
b = b - a;
int n;
cin >> n;
for (int s = 0; s < n; s++)
{
scanf("%d%d", &v[s], &w[s]);
}
sum[0] = 0;
for (int s = 0; s < n; s++)
{
for (int e = w[s]; e <= b ; e++)
{
sum[e] = min(sum[e], sum[e - w[s]] + v[s]);
}
}
if (sum[b]==inf)
{
printf("This is impossible.\n");
}
else
{
printf("The minimum amount of money in the piggy-bank is %d.\n", sum[b]);
}
}
return 0;
} C - 柳予欣的懒惰
暴力查询即可
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct ***
{
int a = 0, b = 0;
};
*** id[6][6];
char map[6][6];
bool link[105][105];
bool vis[105];
int use[105];
int hcnt, rcnt ,n;
void dfsh(int x, int y) {
if (y <= n && map[x][y] == '.') {
id[x][y].a = hcnt;
dfsh(x, y + 1);
}
}void dfsr(int x, int y) {
if (x <= n && map[x][y] == '.') {
id[x][y].b = rcnt;
dfsr(x+1, y );
}
}
int found(int x)
{
for (int s = 1; s < rcnt; s++) {
if (link[x][s] && !vis[s]) {
vis[s] = 1;
if (use[s] == 0 || found(use[s])) {
use[s] = x;
return 1;
}
}
}
return 0;
}
int main()
{
memset(link, 0, sizeof(link));
ios::sync_with_stdio(0);
while (~scanf("%d", &n) && n)
{
memset(id, 0, sizeof(id));
memset(link, 0, sizeof(link));
memset(use, 0, sizeof(use));
hcnt = rcnt = 1;
for (int s = 1; s <= n; s++)
for (int w = 1; w <= n; w++)
cin >> map[s][w];
for (int s = 1; s <= n; s++)
for (int w = 1; w <= n; w++) {
if (map[s][w] == 'X') {
continue;
}
if (id[s][w].a == 0) {
dfsh(s, w);
hcnt++;
}
if (id[s][w].b == 0) {
dfsr(s, w);
rcnt++;
}
link[id[s][w].a][id[s][w].b] = 1;
}
int sum = 0;
for (int s = 1; s < hcnt; s++) {
memset(vis, 0, sizeof(vis));
if (found(s))sum++;
}
// cout << hcnt << " " << rcnt << endl;
printf("%d\n", sum);
}
} D - 柳予欣的愤怒
水题（找规律）实际上把相同的字符放在一起就好了
#include<bits/stdc++.h>
using namespace std;
int main(){
int N;
cin>>N;
string a;
cin>>a;
sort(a.begin(),a.end());
cout<<a<<endl;
return 0;
} E - 柳予欣的骄傲
水题贪心，尽量找用最少的人再次获得+1得分
#include<bits/stdc++.h>
using namespace std;
int sum[100010];
bool cmp(int x,int y){
return (x%10)>(y%10);
}
int main(){
int n,d;
ios::sync_with_stdio(0);
cin>>n>>d;
int ans=0;
for(int i=0;i<n;i++){
cin>>sum[i];
ans+=sum[i]/10;
}
sort(sum,sum+n,cmp);
for(int i=0;i<n;i++){
if(sum[i]==100)continue;
int t=10-sum[i]%10;
if(d-t<0)break;
d-=t;sum[i]+=t;ans++;
}
for(int i=0;i<n;i++){
while(sum[i]<100&&d>=10){
d-=10;sum[i]+=10;
ans++;
}
}
cout<<ans<<endl;
return 0;
}
F - 柳予欣的*欲
水题，特殊判段下就好了。
#include <bits/stdc++.h>
#define maxn 400005
using namespace std;
int a[maxn];
char str[2];
int main()
{
int t;
scanf("%d",&t);
int l=200000;
int r=l-1;
while(t--){
int num;
scanf("%s",str);
scanf("%d",&num);
if(str[0]=='L'){
l--;
a[num]=l;
}
else if(str[0]=='R'){
r++;
a[num]=r;
}
else{
int res=min(a[num]-l,r-a[num]);
cout<<res<<endl;
}
}
return 0;
} G - 柳予欣的嫉妒
emmmmm
#include<bits/stdc++.h>
using namespace std;
int L,v,l,r,ans;
int main()
{
int t;
cin>>t;
while(t--) {
scanf("%d%d%d%d",&L,&v,&l,&r);
ans = (L/v) - (r/v - l/v);
if(l%v==0) ans--;
printf("%d\n",ans);
}
return 0 ;
}
H - 柳予欣的伤悲
emmmmm
#include<bits/stdc++.h>
using namespace std;
int main(){
int a,b;
cin>>a>>b;
if(a>b){
swap(a,b);
}
cout<<a<<" "<<(b-a)/2<<endl;
return 0;
} I - 柳予欣的恐惧
树的直径，详见https://blog.csdn.net/chenshibo17/article/details/82429349
#include<bits/stdc++.h>
using namespace std;
const int maxn = 40010;
const int inf = 0x3f3f3f3f;
int n, fir_d[maxn], vis[maxn], sec_d[maxn];
int head[maxn],cnt;
struct *** {
int u, v, ne, len;
}ed[maxn];
void add(int u, int v, int len) {
ed[cnt].u = u; ed[cnt].v = v;
ed[cnt].len = len; ed[cnt].ne = head[u]; head[u] = cnt++;
}
int dfs(int st,int d[]) {
for (int s = 1; s <= n; s++)
d[s] = inf;
memset(vis, 0, sizeof(vis));
d[st] = 0; vis[st] = 1;
queue<int>q; q.push(st);
int far = 0;
while (!q.empty()) {
int t = q.front(); q.pop(); vis[t] = 0;
far = max(d[t], far);
for (int s = head[t]; ~s; s = ed[s].ne) {
int v = ed[s].v;
if (d[v] > d[t] + ed[s].len) {
d[v] = d[t] + ed[s].len;
if (!vis[v]) {
q.push(v);
vis[v] = 1;
}
}
}
}
for (int s = 1; s <= n; s++)
if (d[s] == far)return s;
}
int main(){
while (~scanf("%d", &n)) {
memset(head, -1, sizeof(head)); cnt = 0;
for (int s = 2; s <= n; s++) {
int a, b;
scanf("%d%d", &a, &b);
add(a, s, b);add(s, a, b);
}
int st = dfs(1, fir_d);
int en = dfs(st, fir_d);
dfs(en, sec_d);
for (int s = 1; s <= n; s++)
printf("%d\n", max(fir_d[s], sec_d[s]));
}
}
J - 柳予欣的女朋友
暴力查询即可。。
#include <bits/stdc++.h>
using namespace std;
int pos[8][2] = { 0,1,1,1,1,0,1,-1,0,-1,-1,-1,-1,0,-1,1 };
char mp[1005][1005];
bool vis[1005][1005];
int n, m;
bool check(int x,int y) {
if (x <= 0 || x > n || y <= 0 || y > m)
return 0;
return 1;
}
bool come(int x, int y, int po) {
for (int i = 0; i < 8; i++) {
if (i == po)continue;
int tx = pos[i][0] - pos[po][0];
int ty = pos[i][1] - pos[po][1];
if (!check(x+tx, y+ty))
return 0;
if (mp[x + tx][y + ty] != '#')
return 0;
}
for (int i = 0; i < 8; i++) {
if (i == po)continue;
int tx = pos[i][0] - pos[po][0];
int ty = pos[i][1] - pos[po][1];
vis[x + tx][y + ty] = 1;
}
return 1;
}
bool dfs(int x, int y) {
for (int i = 0; i < 8; i++) {
if (come(x, y, i)) {
vis[x][y] = 1;
return 1;
}
}
return 0;
}
int main() {
ios::sync_with_stdio(0);
cin >> n >> m;
memset(vis, 0, sizeof vis);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> mp[i][j];
}
}
int flag = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (mp[i][j] == '#' && !vis[i][j]) {
if (!dfs(i, j)) {
flag = 1;
}
}
if (flag)break;
}
if (flag)break;
}
if (flag)
cout << "NO" << '\n';
else
cout << "YES" << "\n";
return 0;
}
Lazada工作强度 32人发布
