2022/5/18

2022/5/18

Tile Painting

很容易就能看出规律，如果一个数没有质因子就输出n，如果有一个就输出这个质因子，如果大于1个就输出1，但我实现不会，淦，之前也看到过这种写法，不过没有重视，这次记下来；

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define lowbit(i) ((-i)&(i))
using namespace std;
const ll inf=1e18;
const ll mod=1e8;
const int maxn=2000006;
ll n;
int main(){//freopen("in.txt","r",stdin);//ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);scanf("%lld",&n);for(ll i=2;i*i<=n;i++){if(n%i==0){while(n%i==0) n/=i;if(n==1) printf("%lld\n",i);else printf("1\n");return 0;}}printf("%lld\n",n);return 0;
}

Minimum Ties

一共有n个队伍，每个队伍互相比一场，赢得队伍加3分，输的不加分，平局都加1分，输出每一场的比赛结果使得所有队伍得分一样且平局尽可能地少；一开始认为只要是奇数就不会有平局，偶数就必须全是平局，但经过半个上午的打表发现偶数也可以有一方队伍胜的情况，通过看规律发现如果n是偶数，那么m=n*(n-1)/2/n就是每个队伍能加多少3，n*(n-1)/2取余n就是多少场平局，而我们刚好发现平局的个数正好是n/2,也就可以分配给[1,2],[3,4],[5,6],,,[n-1,n]这样的场，而其他的场次我们就让其中一个加3，为了避免重复我们开一个数组记录这个队伍赢了几场，赢的场数不超过m，但这样还是不一定符合情况，可能出现某个队伍少加了一场的情况，所以我想了个奇怪的方法，如果i是奇数我就正着枚举，否则我就倒着枚举，试了很多组都没问题，还ac了，就很棒；

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define lowbit(i) ((-i)&(i))
#define x first
#define y second
using namespace std;
const ll inf=1e18;
const ll mod=1e8;
const int maxn=2000006;
ll t,ans[100005],n,ct,tx[110],vis[110];
map<pair<ll,ll>,ll>mm,ma;
map<ll,pair<ll,ll>>mp;
int main(){//freopen("in.txt","r",stdin);//ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);scanf("%lld",&t);while(t--){mp.clear();mm.clear();scanf("%lld",&n);ll m=n*(n-1)/2/n;for(int i=1;i<=n;i+=2) mm[{i,i+1}]=1;for(int i=1;i<=n;i++) tx[i]=0,vis[i]=0;ct=0;for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++) ma[{i,j}]=++ct;for(int i=1;i<=n;i++){if(i&1){for(int j=i+1;j<=n;j++){if(mm[{i,j}]&&n%2==0){ans[ma[{i,j}]]=0;vis[i]++,vis[j]++;continue;}if(tx[i]<m) tx[i]++,ans[ma[{i,j}]]=1,vis[i]+=3;else tx[j]++,ans[ma[{i,j}]]=-1,vis[j]+=3;}}else{for(int j=n;j>i;j--){if(mm[{i,j}]&&n%2==0){ans[ma[{i,j}]]=0;vis[i]++,vis[j]++;continue;}if(tx[i]<m) tx[i]++,ans[ma[{i,j}]]=1,vis[i]+=3;else tx[j]++,ans[ma[{i,j}]]=-1,vis[j]+=3;}}}for(int i=1;i<=n*(n-1)/2;i++) printf("%lld ",ans[i]);printf("\n");
//        for(int i=1;i<=n;i++) cout<<vis[i]<<" ";
//        cout<<endl;}return 0;
}

模拟输出受限制的双端队列 - 题目 - Daimayuan Online Judge

dfs，写了一阵怎么都调不出来，之前就没咋写过dfs，感觉不如bfs直接但是有些地方dfs是很好用的，这次也当练习了，终止条件没写对，队列可以pop掉一个之后再去插新的情况也没有考虑到；

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define lowbit(i) ((-i)&(i))
#define x first
#define y second
using namespace std;
const ll inf=1e18;
const ll mod=1e8;
const int maxn=2000006;
ll n;
char s[110];
set<string>se;
void dfs(ll u,deque<char>q,string t){if(u>n){//终止条件也没对while(!q.empty()) t+=q.front(),q.pop_front();se.insert(t);return;}q.push_back(s[u]);dfs(u+1,q,t);q.pop_back();q.push_front(s[u]);dfs(u+1,q,t);q.pop_front();while(!q.empty()){//忘记了这个地方t+=q.front();q.pop_front();q.push_front(s[u]);dfs(u+1,q,t);q.pop_front();q.push_back(s[u]);dfs(u+1,q,t);q.pop_back();}
}
int main(){//freopen("in.txt","r",stdin);//ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);scanf("%lld",&n);scanf("%s",s+1);deque<char>q;dfs(1,q,"");cout<<se.size()<<endl;for(auto x:se){cout<<x<<endl;}return 0;
}

程序自动分析 - 题目 - Daimayuan Online Judge

给出n个约束条件，问能不能给出恰当的数让这些条件成立，只需要判断是否即可；

如果两个数相等说明两个数有关系，不相等说明没关系，所以这就是并查集了，不过数有点大需要离散化，而且初始化的时候应该是2*n不应该是n，因为2*n个数可能互不相等；

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define lowbit(i) ((-i)&(i))
#define x first
#define y second
using namespace std;
const ll inf=1e18;
const ll mod=1e8;
const int maxn=2000006;
ll t,n,b[300005];
ll s[200005];
ll findd(ll x){return s[x]==x?x:s[x]=findd(s[x]);
}
struct node{ll l,r,e;bool operator<(const node &a)const{return e>a.e;}
}a[100005];
int main(){//freopen("in.txt","r",stdin);//ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);scanf("%lld",&t);while(t--){scanf("%lld",&n);for(int i=1;i<=2*n;i++) s[i]=i;ll m=0;for(int i=1;i<=n;i++){scanf("%lld%lld%lld",&a[i].l,&a[i].r,&a[i].e);b[++m]=a[i].l;b[++m]=a[i].r;}sort(b+1,b+m+1);m=unique(b+1,b+m+1)-b-1;sort(a+1,a+n+1);bool flag=1;for(int i=1;i<=n;i++){if(a[i].e){ll id1=lower_bound(b+1,b+m+1,a[i].l)-b;ll id2=lower_bound(b+1,b+m+1,a[i].r)-b;ll u=findd(id1),v=findd(id2);//cout<<"yes"<<endl;if(u!=v) s[u]=v;}else{ll id1=lower_bound(b+1,b+m+1,a[i].l)-b;ll id2=lower_bound(b+1,b+m+1,a[i].r)-b;ll u=findd(id1),v=findd(id2);if(u==v){flag=0;break;}}}if(flag) printf("YES\n");else printf("NO\n");}return 0;
}//10
//10
//1234567899 1236549875 1
//1236543326 2231365466 1
//1514654654 1236654987 0
//2365446656 4656465651 1
//1351651651 5415616511 1
//1515615165 5165165165 1
//2321326584 1516515156 1
//1561313211 2131654165 1
//1513132121 5614564665 1
//1313213614 5416513231 1

P1983 [NOIP2013 普及组] 车站分级 - 洛谷 | 计算机科学教育新生态 (luogu)

题目意思理解错了， 所以一开始的预处理就是错的，所以越做越难受，之后看了题解大部分说是拓扑排序，确实，是将拓扑排序倒着来了一遍，每次都删掉所有出度为0的点，看看能删几次，因为最后什么也不错也会加1次，最后答案-1就行了，让这题快折磨死了，最大的问题应该还是题意的理解不行吧；

题解 P1983 【车站分级 】 - 黄毛猫_HYX 的博客 - 洛谷博客

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define lowbit(i) ((-i)&(i))
using namespace std;
const ll inf=1e18;
const ll mod=1e8;
const int maxn=2000006;
ll n,m,s[1005],out[1005],vis[1005][1005],vv[1005][1005],bo[1005],maxx;
ll vss[1005][1005],q[1005];
void topo(){ll top;do{top=0;for(int i=1;i<=n;i++){if(out[i]==0&&!bo[i]){q[++top]=i;bo[i]=1;}}for(int i=1;i<=top;i++)for(int j=1;j<=n;j++)if(vis[j][q[i]]) vis[j][q[i]]=0,out[j]--;maxx++;}while(top);}
int main(){//freopen("in.txt","r",stdin);//ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);scanf("%lld%lld",&n,&m);for(int i=1;i<=m;i++){scanf("%lld",&s[i]);for(int j=1;j<=s[i];j++) scanf("%lld",&vv[i][j]),vss[i][vv[i][j]]=1;}for(int i=1;i<=m;i++){for(int j=1;j<=s[i];j++){for(int k=vv[i][1];k<=vv[i][s[i]];k++){if(vss[i][k]) continue;if(!vis[vv[i][j]][k]){vis[vv[i][j]][k]=1,out[vv[i][j]]++;//v[vv[i][j]].push_back(k);}}}}//for(int i=1;i<=n;i++) cout<<out[i]<<" "<<i<<endl;
//	for(int i=1;i<=n;i++){
//        cout<<i<<" st ";
//        for(int j=0;j<v[i].size();j++){
//            cout<<v[i][j]<<" ";
//        }
//        cout<<endl;
//	}topo();printf("%lld\n",maxx-1);return 0;
}

果然看懂题意后我的思路也过了，呀嘞呀嘞；

所有边连完后跑一边dfs去求最长的长度就可以了，写的有点像树形dp了，其实就是个记忆化搜索

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define lowbit(i) ((-i)&(i))
using namespace std;
const ll inf=1e18;
const ll mod=1e8;
const int maxn=2000006;
ll n,m,s[1005],in[1005],vis[1005][1005],vv[1005][1005],dp[1005],maxx;
ll vss[1005][1005];
vector<ll>v[1005];
ll dfs(ll u,ll fa){if(dp[u]) return dp[u];if(v[u].size()<1) return dp[u]=1;for(int i=0;i<v[u].size();i++){ll j=v[u][i];if(j==fa) continue;dfs(j,u);dp[u]=max(dp[u],dp[j]+1);}return dp[u];
}
int main(){//freopen("in.txt","r",stdin);//ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);scanf("%lld%lld",&n,&m);for(int i=1;i<=m;i++){scanf("%lld",&s[i]);for(int j=1;j<=s[i];j++) scanf("%lld",&vv[i][j]),vss[i][vv[i][j]]=1;}for(int i=1;i<=m;i++){for(int j=1;j<=s[i];j++){for(int k=vv[i][1];k<=vv[i][s[i]];k++){if(vss[i][k]) continue;if(!vis[vv[i][j]][k]){vis[vv[i][j]][k]=1,in[k]++;v[vv[i][j]].push_back(k);}}}}
//	for(int i=1;i<=n;i++){
//        cout<<i<<" st ";
//        for(int j=0;j<v[i].size();j++){
//            cout<<v[i][j]<<" ";
//        }
//        cout<<endl;
//	}maxx=0;for(int i=1;i<=n;i++){if(in[i]==0) maxx=max(dfs(i,0),maxx);}printf("%lld\n",maxx);return 0;
}