2019 ICPC Asia Danang Regional Contest
A. Abstract Painting
妙啊~真是妙蛙种子吃着妙脆角妙进了米奇妙妙屋妙到家了
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9+7;
int qpow(int a,int p){
int ans = 1;
while(p){
if(p & 1)ans = (ans * a) % mod;
a = a * a % mod;
p >>= 1;
}
return ans;
}
signed main(){
int T,a,b;
cin >> T;
while(T--){
cin >> a >> b;
cout << qpow(2,a*b)*qpow(3,a+b)%mod << endl;
}
}
B. Banana Problem
题目很长，读懂题意就可以了。直接模拟。
根据特殊点倒过来找猴子。
#include<bits/stdc++.h>
using namespace std;
int n, h, r, s;
const int maxn = 3e5 + 10;
int up[maxn], hor[maxn];
struct rope {
int h, len, to;
bool operator < (const rope& rhs)const {
return h < rhs.h;
}
};
vector<rope>P[maxn];
int main() {
scanf("%d%d%d%d", &n, &h, &r, &s);
for (int i = 0; i < r; i++) {
int len, a, b, H;
scanf("%d%d%d%d", &len, &a, &b, &H);
P[a].push_back(rope{ H,len,b });
P[b].push_back(rope{ H,len,a });
}
for (int i = 1; i <= n; i++) {
scanf("%d%d", up + i, hor + i);
sort(P[i].begin(), P[i].end());
}
int ans = 0;
for (int i = 1; i <= s; i++) {
int pos, nowh, x, y;
scanf("%d%d%d%d", &pos, &nowh, &x, &y);
long long up_dis = 0;
long long hor_dis = 0;
while (1) {
if (P[pos].empty()) {
up_dis += nowh;
break;
}
auto p = lower_bound(P[pos].begin(), P[pos].end(), rope{ nowh,0,0 });
if (p == P[pos].begin()) {
up_dis += nowh;
break;
}
rope x = *prev(p);
up_dis += nowh - x.h;
hor_dis += x.len;
pos = x.to;
nowh = x.h;
}
long long sum = up_dis * up[pos] + hor_dis * hor[pos];
if (sum % (x + y) >= 1 && sum % (x + y) <= x)ans++;
}
printf("%d
", ans);
}
D. Dating time
将钟盘划分成 (43200) 等份，则一秒钟时针走 (1) 格，分针走 (12) 格
算出相对的初始距离，利用相对速度算出最后的相对距离。
遍历这些距离就可以。
#include<bits/stdc++.h>
using namespace std;
int main() {
int h1, m1, h2, m2, p;
int t;
scanf("%d", &t);
while (t--) {
scanf("%d:%d %d:%d %d", &h1, &m1, &h2, &m2, &p);
int s1 = h1 * 3600 + m1 * 60;
int s2 = h2 * 3600 + m2 * 60;
int dx = 12 * (s1 % 3600) - (s1 % 43200);
while (dx < 43200)dx += 43200;
int ans = 0;
int ed = dx + (s2 - s1) * 11;
for (int x = dx; x <= ed; x++) {
if (p == 0) {
if (x % 43200 == 0)ans++;
}
if (p == 90) {
if (x % 43200 == 10800 || x % 43200 == 32400)ans++;
}
if (p == 180) {
if (x % 43200 == 21600)ans++;
}
}
cout << ans << endl;
}
}
G. Generating Numbers
正常模拟就可以。
注意中间有 (1) 的情况，如果第一位大于 (1) 的话，可以省一步
(eg:) (213)
(102 ightarrow 210)
而不是
(102 ightarrow 201)
#include<bits/stdc++.h>
using namespace std;
int main() {
int t;
string s;
cin >> t;
int cnt[20];
cnt[1] = 0;
for (int i = 2; i <= 10; i++) {
cnt[i] = cnt[i - 1] + (i - 2) * 10 + 9;
}
while (t--) {
cin >> s;
if (s.size() == 1) {
cout << s[0] - '1' << endl;
continue;
}
int F = 0;
for (int i = 1; i < s.size(); i++) {
if (s[i] != '0') {
F = 1;
break;
}
}
int ans = 0;
if (!F) { //x0000
ans = 1;
if (s[0] == '1') {
s = string(s.size() - 1, '9');
}
else {
s = string(1, s[0] - 1) + string(s.size() - 1, '9');
}
}
ans += cnt[s.size()];
if (s.size() == 1) {
ans += s[0] - '1';
}
else {
int f = 1;
int ff = 0;
if (s[0] > '1') {
ans += s[0] - '0' + 1;
f = 0;
}
int one = 0;
for (int i = 1; i < s.size() - 1; i++) {
if (s[i] != '0') {
ff++;
if (!f) {
f = 1;
ans--;
}
ans += s[i] - '0';
ans++;
}
if (s[i] == '1')one++;
}
ans += s[s.size() - 1] - '0';
if (!f && s[s.size() - 1] > '0') {
ans--;
}
if (s[0] > '1' && one)ans--;
}
cout << ans << endl;;
}
}
H. Hanjie
二进制预处理出每行可能的数值，直接暴力即可
#include<bits/stdc++.h>
using namespace std;
int r, c;// [1,6]
vector<int>R[10], C[10];
int Cnums[10];
vector<int>Rnums[10];
vector<int>seq;
void cal_seq(int num) {
seq.clear();
int f = 0;
while (num) {
if (num & 1) {
if (!f) {
seq.push_back(1);
}
else {
seq[seq.size() - 1]++;
}
f = 1;
}
else {
f = 0;
}
num >>= 1;
}
reverse(seq.begin(), seq.end());
}
void generate(int row) {
for (int num = 0; num < (1 << c); num++) {
cal_seq(num);
if (seq == R[row]) {
Rnums[row].push_back(num);
}
}
}
int ans = 0;
vector<int>cal;
bool judge() {
memset(Cnums, 0, sizeof Cnums);
for (int i = 0; i < r; i++) {
int num = cal[i];
int cnt = 0;
while (num) {
if (num & 1) {
Cnums[c - cnt] += (1 << (r - i - 1));
}
cnt++;
num >>= 1;
}
}
for (int i = 1; i <= c; i++) {
cal_seq(Cnums[i]);
if (seq != C[i]) {
return false;
}
}
return true;
}
void dfs(int row) {
if (row > r) {
if (judge()) {
ans++;
}
return;
}
for (int i : Rnums[row]) {
cal.push_back(i);
dfs(row + 1);
cal.pop_back();
}
}
int main() {
cin >> r >> c;
for (int i = 1; i <= r; i++) {
int k; cin >> k;
for (int j = 1; j <= k; j++) {
int x; cin >> x;
R[i].push_back(x);
}
}
for (int i = 1; i <= c; i++) {
int k; cin >> k;
for (int j = 1; j <= k; j++) {
int x; cin >> x;
C[i].push_back(x);
}
}
for (int i = 1; i <= r; i++) {
generate(i);
}
dfs(1);
cout << ans << endl;
}
I. Inspecting Illumination
一个交互题，二进制构造就可以了。
挺巧妙的。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 10;
int ans[maxn];
int q[maxn];
int re[maxn];
int cnt;
int n;
int main() {
cin >> n;
int m = 1;
while ((1 << m) - 1 < n)m++;
//cout << m << endl;
for (int i = 1; i <= m; i++) {
cnt = 0;
for (int j = 1; j <= n; j++) {
if (j & (1 << (i - 1))) {
q[++cnt] = j;
}
}
cout << "ASK " << cnt;
for (int k = 1; k <= cnt; k++) {
cout << " " << q[k];
}
cout << endl;
cout.flush();
for (int k = 1; k <= cnt; k++) {
cin >> re[k];
ans[re[k]] += (1 << (i - 1));
}
}
cout << "ANSWER";
for (int i = 1; i <= n; i++) {
cout << " " << ans[i];
}
cout.flush();
}
L. Latin Square
二分图匹配
#include<bits/stdc++.h>
using namespace std;
int A[200][200];
int vis[200];
int nvis[200];
int match[200];
int n, k;
bool dfs(int x) {
for (int i = 1; i <= n; i++) {
if (vis[i] || A[x][i] != 0)continue;
vis[i] = 1;
if (!match[i] || dfs(match[i])) {
match[i] = x;
return true;
}
}
return false;
}
int main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> A[i][j];
nvis[A[i][j]] = 1;
}
}
for (int i = 1; i <= n; i++) {
if (nvis[i])continue;
memset(match, 0, sizeof match);
for (int j = 1; j <= n; j++) {
memset(vis, 0, sizeof vis);
dfs(j);
}
for (int j = 1; j <= n; j++) {
A[match[j]][j] = i;
}
}
cout << "YES" << endl;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cout << A[i][j] << "
"[j == n];
}
}
}
M. Moscow Dream
n >= 3
#include<bits/stdc++.h>
using namespace std;
int main(){
int a,b,c,n;
cin >> a >> b >> c >> n;
string ans[2] = {"NO","YES"};
cout << ans[a>0&&b>0&&c>0&&a+b+c>=n&&n>=3] << endl;
}