acmsguru 101 - Domino

要求每两个相邻的多尼诺骨牌相对的数字相同，即做一个一笔画

#include
using namespace std;
typedef long long ll;
const int maxn = 1e3+;
const ll mod = 1e9 + ;
#define afdafafafdafaf y1;
int ar[maxn], n;

vector ans1, ans2;
int b[maxn], to[maxn], c[maxn], index[maxn];
int head[maxn], cnt;
void add(int u, int v, int index_int, int val){
b[cnt] = v;
c[cnt] = val;
index[cnt] = index_int;
to[cnt] = head[u];
head[u] = cnt++;
}
int vis[maxn], in[maxn], vis_edge[maxn], flag = -, ans_flag = , ins = ;
void dfs(int u,int pre){
vis[u] = ;
for(int i = head[u]; i != -; i = to[i]){
if(vis_edge[i])continue;
int v = b[i];
vis_edge[i] = vis_edge[i ^ ] = ;
dfs(v, u);
ans1.push_back(index[i]);
ans2.push_back(c[i]);
}
}
int inx[maxn], iny[maxn];
int main()
{
cnt = ;
scanf("%d", &n);
for(int i=;i<=;i++)head[i] = -; for(int i=;i && a != pre){
printf("No solution\n");
return ;
}
pre = b;
}
for(int i=ans1.size() - ;i >= ;i--){
int a = ans1[i], b = ans2[i];
printf("%d %c\n", a, b == ? '+' : '-');
}
return ;
}

acmsguru 102 - Coprimes

暴力完事

#include
using namespace std;
typedef long long ll;
const int maxn = 1e3+;
const ll mod = 1e9 + ;
#define afdafafafdafaf y1;
int ar[maxn], n;

int main()
{
scanf("%d", &n);
int ins = ;
for(int i=; i<=n; i++){
if(__gcd(i, n) == )ins++;
}
printf("%d\n", ins);
return ;
}

sguru 103. Traffic Lights

路可以走通的条件是开始走的时候两个路口的颜色一致，dijkstra，每次判断下什么时候可以走，就完事了

#include
using namespace std;
typedef long long ll;
const int maxn = 2e4+;
const ll mod = 1e9 + ;
#define afdafafafdafaf y1;
int ar[maxn], n, m;

char ch[maxn][];
vector > g[maxn];
int main()
{
int s, t;
scanf("%d%d", &s, &t);
s--;
t--;
scanf("%d%d", &n, &m);
//cout << n << ' ' << m << '\n'; vector remain(n, ), am(n, ), bm(n, ), vis(n, ), pre(n, -), dis(n, -);
for(int i=; i & ans){
int re = ;
ans.resize();
if(ch[i][] == 'B'){
re = (am[i] - remain[i] + time) % (am[i] + bm[i]);
}
else{
re = (bm[i] - remain[i] + am[i] + time) % (am[i] + bm[i]);
}
int k = ;
if(re < am[i]){ ans.push_back(am[i] - re); for(int index = ; index < k; index++){ //cout << "index = " << index << '\n'; ans.push_back(bm[i]); ans.push_back(am[i]); } } else{ ans.push_back(am[i] + bm[i] - re); for(int index = ; index < k; index++){ //cout << "index = " << index << '\n'; ans.push_back(am[i]); ans.push_back(bm[i]); } } return re < am[i]; }; priority_queue> qu;
qu.push(make_pair(, s));
int ans_time = , ans_flag = ;
dis[s] = ;
for(; !qu.empty(); ){
int u = qu.top().second;
int now_time = -qu.top().first;
qu.pop();
if(vis[u])continue;
vis[u] = ;
if(u == t){
ans_time = now_time;
ans_flag = ;
break;
}
//cout << "u = " << u << ' ' << u << ' ' << now_time << '\n'; for(int in = ; in < g[u].size(); in++){ int v = g[u][in].first, time = g[u][in].second; if(vis[v])continue; //cout << "v = " << v << '\n'; vector v_u, v_v;
bool time_u = next_time(u, now_time, v_u);
bool time_v = next_time(v, now_time, v_v);
//for(auto x : v_u)cout << x << ' '; cout << '\n'; //for(auto x : v_v)cout << x << ' '; cout << '\n'; int ins = time_u == time_v; int cost = , i = , j = , x = , y = , flag = ; for(;;){ //cout << i << ' ' << j << '\n'; if(x == ){ if(i < v_u.size()){ x = v_u[i++]; } else{ break; } ins ^= ; } if(y == ){ if(j < v_v.size()){ y = v_v[j++]; } else{ break; } ins ^= ; } int mn = min(x, y); if(ins){ cost += time; flag = ; break; } x -= mn; y -= mn; cost += mn; } //cout << "mid\n"; if(flag && (dis[v] == - || dis[v] > now_time + cost)){
qu.push(make_pair(-now_time - cost, v));
dis[v] = now_time + cost;
pre[v] = u;
}
}
}
if(!ans_flag){
printf("0\n");
return ;
}
vector ans;
int x = t;
for(;;){
ans.push_back(x);
if(x == s)break;
x = pre[x];
}
reverse(ans.begin(), ans.end());
printf("%d\n", ans_time);
for(int i = ; i < ans.size(); i++){
printf("%d%c", ans[i] + , i == ans.size() - ? '\n' : ' ');
}
return ;
}

acmsguru 104 - Little Shop of Flowers

经典dp

#include
using namespace std;
typedef long long ll;
const int maxn = 1e2+;
const ll mod = 1e9 + ;
#define afdafafafdafaf y1;
int ar[maxn], n, m;

int arr[maxn][maxn], dp[maxn][maxn];
int main()
{
scanf("%d%d", &n, &m);
for(int i = ; i <= n; i++){ for(int j = ; j <= m; j++)scanf("%d", &arr[i][j]); } int mn = -5e6; for(int i = ; i <= n; i++){ for(int j = ; j <= m; j++)dp[i][j] = mn; } for(int i = ; i <= n; i++){ for(int j = ; j <= m; j++){ int mx = arr[i][j]; if(dp[i - ][j - ] != mn)dp[i][j] = max(dp[i][j], dp[i-][j-] + mx); if(dp[i][j-] != mn)dp[i][j] = max(dp[i][j], dp[i][j-]); } } /* for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++)cout << dp[i][j] << ' '; cout << "\n"; } */ vector ans;
int j = m;
for(int i = n; i >= ; i--){
for(;;){
if(dp[i][j] > dp[i][j-]){
ans.push_back(j);
j--;
break;
}
j--;
}
}
reverse(ans.begin(), ans.end());
printf("%d\n", dp[n][m]);
for(int i = ; i < ans.size(); i++){
printf("%d%c", ans[i], i == ans.size() - ? '\n' : ' ');
}
return ;
}

acmsguru 105 - Div 3

#include
using namespace std;
typedef long long ll;
const int maxn = 1e3+;
const ll mod = 1e9 + ;
#define afdafafafdafaf y1;
int ar[maxn], n;

int main()
{
ll n;
while(scanf("%lld", &n) != EOF){
ll ans = n / * ;
ans += (n % ) == ;
printf("%lld\n", ans);
}
return ;
}

acmsguru  106 - The Equation

debug了无数次，坑比较多，慢慢填

除数不要为0，逻辑太复杂

#include
using namespace std;
typedef long long ll;
const int maxn = 1e3+;
const ll mod = 1e9 + ;
#define afdafafafdafaf y1;
int ar[maxn], n;

void exgcd(ll a,ll b,ll& d,ll &x,ll &y)
{
if(!b){
d=a,x=,y=;
}
else
{
exgcd(b,a%b,d,y,x);
y-=x*(a/b);
}
}
int main()
{
int aa,bb,cc,xx1,xx2,yy1,yy2;
scanf("%d%d%d", &aa, &bb, &cc);
scanf("%d%d", &xx1, &xx2);
scanf("%d%d", &yy1, &yy2);
double a = aa,b = bb, c = cc, x1 = xx1, x2 = xx2, y1 = yy1, y2 = yy2;
double xy1, xy2;
assert(xx1 <= xx2); assert(xx1 <= xx2); ll ans = ; if(aa == && bb == ){ if(cc == ){ ans = 1LL * (yy2 - yy1 + ) * (xx2 - xx1 + ); } else{ ans = ; } } else if(aa == ){ if(cc % bb == && - cc / bb <= y2 && - cc / bb >= y1)ans = x2 - x1 + ;
else ans = ;
}
else if(b == ){
if(cc % aa == && - cc / aa <= x2 && - cc / aa >= x1)ans = y2 - y1 + ;
else ans = ;
}
else{
ll dd, xx, yy;
exgcd(aa, bb, dd, xx, yy);
dd = abs(dd);
if(cc % dd == ){
if(aa < )dd *= -;
aa /= dd;
bb /= dd;
cc /= dd;
a = aa;
b = bb;
c = cc;
xx *= -cc;
yy *= -cc;
//cout << aa << ' ' << bb << ' ' << cc << '\n';
//cout << xx << ' ' << yy << '\n';
assert(aa * xx + bb * yy + cc == );
xy1 = (-c - a * x1) / b;
xy2 = (-c - a * x2) / b;
y1 = max(y1, min(xy1, xy2));
y2 = min(y2, max(xy1, xy2));
//cout<<y1<<" "<<y2<<"\n";
y1 = ceil((y1 - yy) / aa);
y2 = floor((y2 - yy) / aa);
ans = y2 - y1 + ;
ans = max(ans, 0LL);
}
else{
ans = ;
}
}
printf("%lld\n", ans);
return ;
}

107 - 987654321 problem

有8个数的平方符合规则

x x * x

所以枚举就完事了

#include
using namespace std;
typedef long long ll;
const int maxn = 1e3+;
const ll mod = 1e9 + ;
#define afdafafafdafaf y1;
int ar[maxn], n;

void exgcd(ll a,ll b,ll& d,ll &x,ll &y)
{
if(!b){
d=a,x=,y=;
}
else
{
exgcd(b,a%b,d,y,x);
y-=x*(a/b);
}
}
vector v;
ll s = ;
void dfs(ll x, ll last, ll pre, ll base = ){
if(x == ){
//cout << "s = " << pre << " " << pre * pre << "\n";
return ;
}
if(x <= ){
return ;
}
for(int i=;i<;i++){
ll mid = i * pre * + i * i * base + last;
if(mid % == x % ){
dfs(x / , mid / , pre + base * i, base * );
}
}
}
int main()
{
ll x = ;
//dfs(x, 0, 0, 1);
scanf("%lld\n", &x);
if(x < ){
printf("0\n");
}
else if(x == )printf("8\n");
else{
printf("");
for(int i = ; i < x - ; i++)printf("");
printf("\n");
}
return ;
}

108 - Self-numbers II

暴力

#include
using namespace std;
typedef long long ll;
const int maxn = 1e7+;
const int maxm = 5e3+;
const ll mod = 1e9 + ;
#define afdafafafdafaf y1;
int ar[], n, m;
bool is[maxn];
int check(int x){
int pre = x;
int ins = ;
while(x > ){
ins += x % ;
x /= ;
}
return ins + pre;
}
pair p[maxm];
int main()
{
scanf("%d%d", &n, &m);
for(int i=;i<=m;i++){
scanf("%d", &p[i].first);
p[i].second = i;
}
sort(p+, p+m+);
int ins = , pre = ;
ll ans = ;
for(int i=;i<=n;i++){
if(i % != )pre += ;
else pre = check(i);
if(pre < maxn)is[pre] = ;
if(!is[i]){
ans++;
while(ins <=m && p[ins].first == ans){
ar[p[ins].second] = i;
ins++;
}
}
}
printf("%lld\n", ans);
for(int i=;i<=m;i++){
printf("%d%c", ar[i], i == m ? '\n' : ' ');
}
return ;
}

109 -

看不懂

110 -

疑似题意：给你n个球体和一条射线，射线到达球体表面会反射；问射线折射到达的前10个球体ID，不足十个全部输出

窝太菜了

acmsguru 552 - Database Optimization

充分利用STL即可

#include
using namespace std;
typedef long long ll;
const int maxn = 1e6+;
const ll mod = ;
const int sz = ;
#define afdafafafdafaf y1;
int n,m;
int ar[maxn];
map mp;
int ins=;
map, int> ms;
int decode(string s){
if(mp.count(s) == ){
mp[s] = ins++;
}
return mp[s];
}
vector res, in;
void dfs(int x){
if(x==in.size()){
if(res.size() == )return ;
vector mid = res;
sort(res.begin(), res.end());
ms[res]++;
res = mid;
}
else{
dfs(x+);
res.push_back(in[x]);
dfs(x+);
res.pop_back();
}
}
char ch[maxn];
int main()
{
scanf("%d", &n);
for(int i=; i<=n; i++){
int k;scanf("%d", &k);
in.resize();
while(k--){
scanf("%s", ch);
in.push_back(decode(string(ch)));
}
dfs();
assert(res.size() == );
}
scanf("%d", &m);
for(int i=; i<=m; i++){
int k;scanf("%d", &k);
in.resize();
while(k--){
scanf("%s", ch);
in.push_back(decode(string(ch)));
}
sort(in.begin(), in.end());
printf("%d\n", ms[in]);
}
return ;
}