2022/5/18

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

#include
#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("%lldn",i);
            else printf("1n");
            return 0;
        }
    }
    printf("%lldn",n);
	return 0;
}

一共有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
#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,ll>mm,ma;
map>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]i;j--){
                    if(mm[{i,j}]&&n%2==0){ans[ma[{i,j}]]=0;vis[i]++,vis[j]++;continue;}
                    if(tx[i] 
模拟输出受限制的双端队列 - 题目 - Daimayuan Online Judge 
dfs，写了一阵怎么都调不出来，之前就没咋写过dfs，感觉不如bfs直接但是有些地方dfs是很好用的，这次也当练习了，终止条件没写对，队列可以pop掉一个之后再去插新的情况也没有考虑到；
 
#include
#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];
setse;
void dfs(ll u,dequeq,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);
	dequeq;
	dfs(1,q,"");
	cout< 
程序自动分析 - 题目 - Daimayuan Online Judge 
给出n个约束条件，问能不能给出恰当的数让这些条件成立，只需要判断是否即可；
 
如果两个数相等说明两个数有关系，不相等说明没关系，所以这就是并查集了，不过数有点大需要离散化，而且初始化的时候应该是2*n不应该是n，因为2*n个数可能互不相等；
 
#include
#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"< 
P1983 [NOIP2013 普及组] 车站分级 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 
题目意思理解错了， 所以一开始的预处理就是错的，所以越做越难受，之后看了题解大部分说是拓扑排序，确实，是将拓扑排序倒着来了一遍，每次都删掉所有出度为0的点，看看能删几次，因为最后什么也不错也会加1次，最后答案-1就行了，让这题快折磨死了，最大的问题应该还是题意的理解不行吧；
 
题解 P1983 【车站分级 】 - 黄毛猫_HYX 的博客 - 洛谷博客
 
#include
#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< 
果然看懂题意后我的思路也过了，呀嘞呀嘞；
 
所有边连完后跑一边dfs去求最长的长度就可以了，写的有点像树形dp了，其实就是个记忆化搜索
 
#include
#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];
vectorv[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