AtCoder Beginner Contest 204
[C - Tour]
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
/*
整体思路:
判别每个端点root 能到的其它端点
用vis标记
*/
int n,m,sum=0;
vector<int>g[2005];
int vis[2005];
void dfs(int root){
if(vis[root]) return ;//
vis[root]++;
for(auto t:g[root]) dfs(t);
}
int main(){
cin >> n >>m;
for(int i=0;i<m;i++){
int a,b;
cin >> a >> b;
g[a-1].push_back(b-1);
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++) vis[j]=0;
dfs(i);
for(int j=0;j<n;j++) {
if(vis[j]) sum++;
}
}
cout<<sum<<endl;
return 0;
}
编码1.0
#include <bits/stdc++.h>
using namespace std;
const int mod = 1000007;
string s;
int dp[50];
//001A 7
void solve()
{
string a;
cin >> a;
for(int i=0;i<a.size();i++)
{
int k;
if(a[i]<='9') k=a[i]-'0';//数字
else k = a[i]-'A'+10;//十六进制
dp[k]=0;
for(int j=0;j<k;j++)
{
dp[k]+=dp[j];//到该数肯定包含前面的所有情况
}
dp[k]++;//dp[0]=1,dp[1]=2,dp[10]=4;
//加上自身
}
int res = 0;
for(int i=0;i<17;i++) //cout << dp[i] << endl;
res+=dp[i];
cout << res;
}
int main()
{
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
int _=1;
//cin>>_;
for(_;_--;)
{
solve();
}
return 0;
}
精简写法贴上:
#include<bits/stdc++.h>
using namespace std;
char s[1000010];
int dp[20],t, ans = 0;
int main(){
cin >> s;
int len = strlen(s);
for(int i = 0; i < len; i++)
{
if(s[i] >= '0' && s[i] <= '9') t = s[i] - '0';
else t = s[i] - 'A' + 10;
int sum = 1;
for(int j = 0; j < t; j++) sum += dp[j];
dp[t] = sum;
}
for(int i = 0; i <= 15; i++) ans += dp[i];
cout << ans;
}
AISing Programming Contest 2021(AtCoder Beginner Contest 202)
D - aab aba baa
https://www.cnblogs.com/ChivasRegal/p/14827125.html
https://blog.csdn.net/m0_57255454/article/details/117221872
http://acm.hdu.edu.cn/search.php?field=problem&key=+ACM%CA%EE%C6%DA%BC%AF%D1%B5%B6%D3%C1%B7%CF%B0%C8%FC%A3%A8%C8%FD%A3%A9&source=1&searchmode=source
用k 与 c[i][j]来判断首位是否为'a'
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll c[65][35];
string s;
void get_c(){//杨辉三角构建组合数
for(int i=0;i<65;i++) c[i][0] = 1;
for(int i=0;i<65;i++){
for(int j = 1;j<=i && j<35;j++){
c[i][j] = c[i-1][j]+c[i-1][j-1];
}
}
}
int main(){
get_c();
ll a,b,k;
cin >> a >> b >>k;
while(k>1){
if(k>c[b+a-1][a-1]){
k-=c[b+a-1][a-1];
b--;
s+="b";
}
else{
a--;
s+="a";
}
}
for(int i=0;i<a;i++) s+="a";
for(int i=0;i<b;i++) s+="b";
cout<<s<<endl;
}
AtCoder Beginner Contest 207
B - Hydrate
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
/*
a b c d
5 2 3 2
x(cd-b)>=a
x的范围为[0,a]
*/
int main(){
ll a,b,c,d;
cin >> a >> b >> c >>d;
ll e= 1,f=0;
if(c*d>b){
ll den=c*d-b;
ll ans=(double)(a+den-1)/den;
cout<<ans<<"\n";
}
else cout<<"-1"<<endl;
return 0;
}
AtCoder Beginner Contest 209
[C - Not Equal]
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+10;
const ll mod = 1e9+7;
int main(){
ll n;cin >> n;
ll c[n];
for(int i=0;i<n;i++) {
cin >> c[i];
}
sort(c,c+n);
ll sum =1;
for(int i=0;i<n;i++){
sum*=c[i]-i;
sum%=mod;
}
cout<<sum%mod<<endl;
return 0;
}
AtCoder Beginner Contest 211
C - chokudai
/*
题意:找出字符串有多少个子串是"chokudai".
思路:"chokudai"长度很小,直接DP。
f(i,j)表示用字符串前i个字符的子串形成"chokudai"前j个字符的方案数。
如果s[i]等于"chokudai"第j个字符:f (i,j) = f (i-1,j) + f (i-1, j-1)
如果不等于:f (i,j) = f ( i-1,j)
注意初始化,f (i,0 ) = 1
*/
#include<bits/stdc++.h>
using namespace std;
string s;
string s1="chokudai";
const int N = 1e5+10;
int dp[N][9];
int main(){
cin>>s;
int len = s.size();
for(int i=0;i<len;i++) dp[i][0] =1;
for(int i=1;i<=len;i++){
for(int j=1;j<=8;j++){
if(s[i-1]==s1[j-1])
dp[i][j] = dp[i-1][j]+dp[i-1][j-1];
else dp[i][j] = dp[i-1][j];
dp[i][j] %= 1000000007;
}
}
cout<<dp[len][8]<<endl;
return 0;
}
AtCoder Beginner Contest 212
C - Min Difference
/*
注意数组的数据范围为2e5
考虑的时间复杂度为O(n),O(nlog)
*/
#include<bits/stdc++.h>
using namespace std;
const int inf = 1e9;
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int n,m;cin >> n >> m;
int a[n],b[m];
for(int i=0;i<n;i++) cin >> a[i];
for(int i=0;i<m;i++) cin >> b[i];
sort(a,a+n);
sort(b,b+m);
int x=0,y=0;
int ans = inf;
while(x<n && y<m){
ans = min(ans,abs(a[x]-b[y]));
if(a[x]>b[y]) y++;
else x++;
}
cout<<ans<<endl;
}
int ans = inf;
for(int i=0;i<n;i++){
for(int j=idx;j<m;j++){
ans = min(ans,abs(a[i]-b[j]));
if(b[j]>=a[i]){
idx = j;
break;
}
else idx = m;
}
}
cout<<ans<<endl;
}
D - Querying Multiset
/*
每次遇到 3 取出包中最小的数字
需要从小到大排序且重复想到multiset
或者是优先队列最小堆
*/
//multiset与set的区别:multiset支持重复,而set会去重
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll q,ty,x,sum=0;
multiset<ll> s;
cin >> q;
while(q--){
cin >> ty;
if(ty==1){
cin >> x;
s.insert(x-sum);//使得每两个数的相对大小关系不变
}
else if(ty==2){
cin >> x;
sum+=x;
}
else if(ty==3){
cout<<*s.begin()+sum<<endl;
s.erase(s.begin());
}
}
return 0;
}
采用优先队列(小根堆)
priority_queue<long long, vector<long long>, greater<long long> > p;
p.push(x-sum);
p.top()+sum;
p.pop();
AtCoder Beginner Contest 213
[C - Reorder Cards]
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
int main(){
int h,w,n;
cin >> h >> w >> n;
vector<pair<int,int> > s(n);
set<int> nx,ny;
for(int i=0;i<n;i++){
cin >> s[i].x >> s[i].y;
nx.insert(s[i].x);
ny.insert(s[i].y);
}
int cnt1=1,cnt2=1;
map<int,int>mx,my;
for(int i:nx){
mx[i] = cnt1;
cnt1++;
}
for(int i:ny){
my[i] = cnt2;
cnt2++;
}
for(int i=0;i<n;i++){
cout<<mx[s[i].x]<<" "<<my[s[i].y]<<endl;
}
return 0;
}
[D - Takahashi Tour]
/*
题意:
子节点存在没有访问过的城市,去字典序较小的城市
如果不存在,判断当前是否在城市 1 的位置
否则返回原路
思路:很裸的dfs,注意要对顶点里面的子节点要从小到大排序
*/
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
typedef long long ll;
vector<int> g[N];
int vis[N];
void dfs(int root){
vis[root]=true;
for(auto t:g[root]){
if(vis[t]==0){
cout<<root<<" ";
dfs(t);
}
}
cout<<root<<" ";
}
int main(){
int n,x,y;cin >> n;
for(int i =0;i<n-1;i++){
cin >> x >>y;
g[x].push_back(y);
g[y].push_back(x);
}
for(int i =1;i<=n;i++){
sort(g[i].begin(),g[i].end());
}
dfs(1);
return 0;
}
KYOCERA Programming Contest 2021(AtCoder Beginner Contest 200)
C - Ringo’s Favorite Numbers 2
#bogedaye
#include<bits/stdc++.h>
using namespace std;
/*
//1.法1:埃氏筛的思想,我的做法,核心是统计每一类的个数,然后用排列组合公式
const int N = 2e5+10;
typedef long long LL;
LL ans;
int a[N];
bool vis[N];
int main() {
int n;
cin>>n;
for(int i = 1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++){
if(vis[i])continue;//加了vis[]数组标记已经访问过了
LL cnt=0;
for(int j=i+1;j<=n;j++){
if((a[i]-a[j])%200==0){
cnt++;
vis[j]=true;
}
}
ans+=cnt*(cnt+1)/2;
}
cout<<ans<<endl;
return 0;
}
*/
//法2:核心思想也是统计每一类的个数 但是这个是手动模拟了一下加的过程
const int N=2e5+10;
typedef long long LL;
LL ans;
int a[N];
int x;
int main(){
int n;
cin>>n;
//2.1手动模拟组合公式推导的过程 swc的解法
// for(int i=1;i<=n;i++){
// cin>>x;
// x%=200;
// if(a[x]) ans+=a[x];
// a[x]++;
// }
//2.2进一步优化 editorial提供的解法
for(int i=1;i<=n;i++){
cin>>x;
a[x%200]++;
}
for(int k=0;k<200;k++){
ans+=(LL)a[k]*(a[k]-1)/2;//这里要加LL 不然会爆掉
}
cout<<ans<<endl;
}
AtCoder Beginner Contest 183
[C - Travel]
法一:next_permutation()
#include<bits/stdc++.h>
using namespace std;
int a[8][8];
int main(){
int n,k;
cin >> n >>k;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)
cin >> a[i][j];
}
vector<int>p;
for(int i=1;i<n;i++) p.push_back(i);
int ans =0;
do{
int tot = a[0][p[0]];
for(int i=0;i<n-2;i++) tot+=a[p[i]][p[i+1]];
tot+=a[p.back()][0];
if(tot==k) ++ans;
}while(next_permutation(p.begin(),p.end()));
cout<<ans<<endl;
}
法二:dfs函数
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll g[10][10],vis[10],ans=0,n,k;
void dfs(int cnt,ll sum,int last){
if(cnt==n){
if(sum+g[last][1]==k)ans++;
return ;
}
cnt++;
for(int i=2;i<=n;i++){
if(vis[i]==0){
vis[i]=1;
dfs(cnt,sum+g[last][i],i);
vis[i]=0;
}
}
}
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)cin>>g[i][j];
vis[1]=1;
dfs(1,0,1);
cout<<ans;
return 0;
}