Panasonic
Programming Contest (AtCoder Beginner Contest 186)
A
1
2
3
4
5
6
7
8
9
10
11
| #include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+100;
int main()
{
int n,m;
cin>>n>>m;
cout<<n/m;
return 0;
}
|
B
求出最小值，然后减去
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+100;
int mp[105][105];
int main()
{
int mx = 99999999;
int n, m; cin >> n >> m;
for(int i = 1;i <= n; i++) {
for(int j = 1;j <= m; j++) {
cin >> mp[i][j];
mx = min(mx, mp[i][j]);
}
}
ll ans = 0;
for(int i = 1;i <= n; i++) {
for(int j = 1;j <= m; j++) {
ans += mp[i][j] - mx;
}
}
cout << ans;
}
|
C
直接分解10和分解8然后判断会不会出现7
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| #include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+100;
int main()
{
int n; cin >> n;
ll ans = n;
for(int i = 7;i <= n; i++) {
int tt = i;
bool flag1 = 0;
while(tt) {
if(tt % 10 == 7) {
flag1 = 1;
break;
}
tt /= 10;
}
tt = i;
bool flag2 = 0;
while(tt) {
if(tt % 8 == 7) {
flag2 = 1;
break;
}
tt /= 8;
}
if(flag1 || flag2) ans--;
}
cout << ans << endl;
}
|
D
排序不影响，排序后求一个前缀和就可以了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| #include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+100;
ll a[N];
ll ans;
ll sum[N];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
sort(a+1,a+1+n);
for(int i=1;i<=n;i++)
{
sum[i]=sum[i-1]+a[i];
}
for(int i=1;i<n;i++)
{
ans+=(sum[n]-sum[i])-(n-i)*a[i];
}
cout<<ans;
}
|
E
由于可以转化为同余问题，就扩展欧几里得直接解决即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+100;
ll x,y;
ll exgcd(const ll &a,const ll &b)
{
if(!b)
{
x=1;
y=0;
return a;
}
ll d=exgcd(b,a%b);
ll z=x;
x=y;
y=z-y*(a/b);
return d;
}
int main()
{
int t;
cin>>t;
while(t--)
{
ll a,b,s;
cin>>b>>s>>a;
ll g=exgcd(a,b),t=(b-s)%b;
if(t%g)
{
cout<<-1<<'\n';
}
else
{
cout<<(x%b+b)%b*(t/g)%(b/g)<<'\n';
}
}
}
|
F
显然要维护: r[i]=第i行第一个障碍的下标,
c[i]=第i列第一个障碍的下标.
对于[1,c[1]-1]的每一行,显然答案累加r[i]-1,
对于[1,r[1]-1]的每一列,显然答案累加c[i]-1,
但是这样会统计到之前统计过的格子,考虑如何消去重复:
对于第i列,本来应该累加c[i]-1,
重复格子的个数就是1到c[i]-1行中r[]>i的行的数量,
那么不重复格子的数量就是1到c[i]-1行中r[]<=i的行的数量. 如何统计?
上面的条件是r[]<=i,发现i是递增的,
因此将(r[k],k)按照第一维r[]从小到大排序,
枚举列i的时候,只需要查询r[]<=i的(r[k],k)中,
有多少个满足k满足<=c[i]-1即可, 可以用树状数组存k,
查询的时候直接查询[1,c[i]-1]的前缀和即可.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
| #include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e6+5;
vector<ll>g[N];
ll r[N],c[N];
ll n,m,w;
struct BIT
{
ll c[N];
int lowbit(ll i)
{
return i&(-i);
}
void add(ll i,ll t)
{
while(i<N)
{
c[i]+=t;
i+=lowbit(i);
}
}
int ask(ll i)
{
ll res=0;
while(i)
{
res+=c[i];
i-=lowbit(i);
}
return res;
}
}T;
ll ans;
int main()
{
cin>>n>>m>>w;
for(int i=1;i<=n;i++)
{
r[i]=m+1;
}
for(int i=1;i<=m;i++)
{
c[i]=n+1;
}
for(int i=1;i<=w;i++)
{
ll x,y;
cin>>x>>y;
r[x]=min(r[x],y);
c[y]=min(c[y],x);
}
for(int i=1;i<=c[1]-1;i++)
{
ans+=r[i]-1;
}
for(int i=c[1];i<=n;i++)
{
r[i]=1;
}
for(int i=1;i<=n;i++)
{
g[r[i]].push_back(i);
}
for(int i=1;i<=m;i++)
{
if(c[i]==1)
{
break;
}
ans+=T.ask(c[i]-1);
for(auto j:g[i])
{
T.add(j,1);
}
}
cout<<ans;
}
|
