정경 초청 경기 2266:number(집합)

2705 단어 잡담
n을 주고 x를 몇 개나 세느냐고 물어보면 y가 만족한다.
x, y∈[1, n], x < y
       x, y    [0, 9]       

입력
정수 n (n <= 107) 출력
하나의 숫자, 즉 답안 예시 입력 출력
30
샘플 출력
3
프롬프트
<1, 11> <2, 22> <12, 21>
다음 코드는 비교적 좋은 것 같지만, 그래도 시간을 초과할 것이며, 새로운 사고방식이 있으면 다시 갱신할 것이다
#include
#define ll long long
#define inf 0x3f3f3f3f
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define rep1(i,b,a) for(int i=b;i>=a;i--)
using namespace std;
const int N=1e7+100;
int vis1[N];
int arr[10];
int main()
{
    ll ans=0;
    int n;
    cin>>n;
    map<set<int>,ll>mp;
    for(int i=1;i<=n;i++)
    {
        set<int>st;
        int t=i;
        while(t)
        {
            int a=t%10;
            if(!st.count(a))
            st.insert(a);
            t/=10;
        }
        ll sum1=0;
        for(set<int>::iterator it=st.begin();it!=st.end();it++)
            sum1=sum1*10+*it;
        ans+=vis1[sum1];
        vis1[sum1]++;
    }
    cout<return 0;
}

좋은 웹페이지 즐겨찾기